[프로그래머스] 큰 수 만들기(JavaScript)

코딩테스트 연습 - 큰 수 만들기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

---

난이도 : Level 2

 

풀이 과정 :

제거하려는 수가 k개라면 제거한 후 남는 문자열 길이는 문자열.length - k 이다.

 

나는 제거하려는 수를 기준으로 안두고 length-k로 만들 수 있는 최대 수를 기준으로 하였다.

 

제거 하여 가장 큰 수가 되기 위해서는

length-k (제거후 남는 문자열 길이) 가 남는 한에서 처음으로 오는 수가 가장 커야한다.

예를들어 본 예제인 1924에서 가장 처음으로 오는 수는 9 여야 하는 것

 

이러한 방식으로 반복문을 돌려주며 큰 수를 맞춰나가면 된다.

글로 설명하니 복잡한 느낌인데 코드를 보면 이해 갈 듯?

 

그리고 맨 처음에는 slice 메서드를 이용해서 배열을 잘라 최대값을 찾아주었는데

위와 같이 할 시 테스트케이스 10번에서 시간초과가 난다..

배열의 크기가 백만이고, k도 최소 1이라서 최대 연산개수가 백만*백만이라 꽤 많은 시간을 잡아먹는 것 같다.

그리고 자연수가 최대 9이기 때문에 효율성을 위해 최대 값이 9가나오면 반복문을 바로 종료시켜주었음

 

++ 추가로 다른 분 코드 보면서 알게 된점

배열이 비어있어도 pop()이 가능함 (에러나는 줄 알았음)

배열의 유효하지 않은 인덱스의 값을 반환하면 undefined

예를들어 arr[-1] 은 에러가 나는게 아니라 undefiend임..

 

 

 

 

코드 :

// 가장 큰 수가 되려면
// k의 개수가 남는 한에서 첫 숫자가 제일 커야됨
// 그다음 k-1이 남는 한에서 두번째 숫자가 제일 커야됨
// ...
function solution(number, k) {
    var answer = '';
    
    number = number.split("");
    
    let idx = 0;
    k = number.length - k;
    while(k--){                
        let max_num = -1;
        
        for(let i=idx;i<number.length-k;i++){
            if(number.length - (i+1) < k) break;
            if(max_num < number[i]) {
                max_num = number[i];
                idx = i+1;        
                if(max_num == 9) break;
            }
        }        
        answer += max_num;
  		// 큰 수가 더해지는 방식
    }
    return answer;
}