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

문제 설명

https://programmers.co.kr/learn/courses/30/lessons/42883?language=javascript

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

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

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

나의 풀이

첫 번째 풀이

function solution(number, k) {
    let answer = 0;
    
    function pickWithout(n, shouldDeleteNum) {
        if (shouldDeleteNum === 0) {
            answer = answer < +n? +n : answer;
        }
        for(let i =0; i < n.length; i++) {
            const deletedOneNum = n.substring(0,i)+ n.substring(i+1);
            pickWithout(deletedOneNum, shouldDeleteNum -1);
        }
    }
    
    pickWithout(number, k);
    
    return answer.toString();
}

두 번째 풀이

function solution(number, k) {

    const stack = [];

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

        while (stack[stack.length-1] < number[i] && 0 < k) {
            stack.pop();
            k--;
        }
        stack.push(number[i]);
    }

    stack.splice(stack.length - k, k);

    return stack.join('');;
}

풀이 회고

재귀를 이용해서 쉽게 풀었다고 생각했는데 시간 초과가 나왔다. 문제를 풀고 나서 보니 number가 1,000,000자리까지 가능해서 지나치게 오래 걸린 것 같다. 두 번째 풀이는 다른 분의 도움을 받아서 풀었는데 결국에 앞부터 스택에 넣고 스택에는 k개를 삭제할 때까지는 위로 갈 수록 작아지는 스택을 유지하는 것이 키 포인트였다.