[프로그래머스] 큰 수 만들기 (Lv.2) - javascript

문제

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

• 제한 조건
  • number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
  • k는 1 이상 number의 자릿수 미만인 자연수입니다.
     

풀이

1차 풀이

function solution(number, k) {

    let answer = [];

    number = number.split('');

    function permutation(arr, selectNum) {

        let result = [];
        if(selectNum === 1) return arr.map(v => [v]);

        arr.forEach((v, idx, arr) => {
            let fixed = v;
            let restArr = arr.filter((v,index) => index !== idx);
            let permutationArr = permutation(restArr, selectNum -1);
            let combineArr = permutationArr.map(v => [fixed, ...v]);
            result.push(...combineArr);
        });
        return result;
    }

    // answer = permutation(number, number.length - k)
    answer = permutation(number, number.length - k).map(v => +v.join(''));

    // return Math.max(null, answer)
    return Math.max.apply(null, answer);

}

 
문제를 제대로 이해하고 못하고 풀었기에 문제가 생겼다.
일단 숫자를 제외하고 남은 수를 얻는 과정을 잘못 이해했다.
제외하고 순서대로 보는 것이 아닌, 숫자를 number.length - k 개를 뽑는 순열과 같다고 이해했다.
그래서 순열을 구하고 그 중에서 최대값을 구한 것이다.
 
결과는 역시 통과하지 못했고, 시간 제한에도 걸렸다.
n이 1,000,000자리 숫자 미만이기 때문에 순열을 구하면 절대 효율적이지 못하다.
 

모범 답안

function solution(number, k) {

    const stack = []; // 남은 숫자들이 저장될 스택

    for (let i = 0; i < number.length; i++) {

        let el = number[i]; // 현재 요소

        // 제거가능한 숫자 남아있음 && el이 스택 맨 위보다 클 때
        while(k > 0 && el > stack[stack.length-1]) {

            stack.pop(); // 맨 위 숫자 꺼냄
            k--; // 제거 숫자 하나 줄어듬
        }
        stack.push(el);
    }

    return stack.slice(0, number.length - k).join('');
}

 

1. 첫번째 요소는 비교대상이 없기 때문에 (stack[stack.length -1] = undefined 라서 for문 통과함) 무조건 stack에 추가된다.
    
2. 그 다음 값은 stack의 top 요소와 비교해서 작으면 stack에 추가되고, 크다면 stack에 있던 수를 빼고 추가된다.
   여기서 빠진 수가 제외된 숫자가 되는 것이다. 이 과정에서 제외 가능한 숫자인 k도 하나 줄어든다.
    
3. 맨 마지막 숫자까지 for문을 통과해도 k가 0이 아닌 경우가 있기 때문에 이를 처리해야한다.
   바로 '7777777' 같이 각 자릿수가 같아서 비교가 불가한 경우가 대표적이다.
   위 숫자가 for문을 거친다면 stack = '7777777' / k = 4 가 된다.
   그러므로 k 만큼 뒤에서 요소를 제외한 배열을 만든다.
    
4. stack을 문자열로 바꿔 반환한다.
    

• 정확도 테스트 결과

  

  
   

---

참고

taesung1993.tistory