프로그래머스 [Lv. 2] 큰 수 만들기 {언어 : JavaScript} [시간 초과 해결]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

정답 코드

function solution(number, k) {
    const n = number.length;
    let wish = n - k;
    const stack = [];
    let idx = 0;
    while (idx < n && wish) {
        let maxV = -1;
        let currentIdx = idx;
        for (let jdx=idx; jdx <= idx+k; jdx++) {
            const value = number[jdx];
            if (value > maxV) {
                maxV = value;
                currentIdx = jdx;
            };
            // 최대 값이 9 이면 그 이상 찾을 필요가 없기 때문에 종료한다.
            if (maxV == 9) {
                break;
            };
        };
        stack.push(maxV);
        k -= currentIdx - idx;
        idx = currentIdx + 1;
        wish -= 1;
    };
    
    const answer = stack.join("");
    return answer;
}

풀이 방법

1. idx가 number의 길이와 같거나 k개를 제거하고 남아야 하는 숫자를 충족하는 경우 종료된다.
2. 현재 idx에서 k를 더한 범위까지의 값 중 가장 큰 값을 stack에 넣는다.
3. 이 과정에서 최대값이 이미 9라면 뒤를 더 찾을 필요가 없으므로 break로 멈춘다. => 이 부분이 시간 초과 해결 방법
   1. 9보다 큰 수가 없으니 멈추는게 맞고 다음과 같은 문제를 해결해준다.
   2. 9가 100만개로 이루어진 숫자에서 49만9999개를 제외해야 하는 경우 시간 초과가 발생하게 된다.
4. 여튼 이런 과정을 거쳐서 answer를 반환한다고 하면 뭔 소리인지 모를 수도 있으니 다음과 같은 과정이라고 보면 된다.
   1. 516718283라는 숫자가 있다고 치고 4개를 제거할 수 있다고 하자.
   2. 5에서 시작하면 1 6 7 1 중에서 7이 가장 크므로 7 앞의 3개를 제거 한다.
   3. 7 뒤의 1에서 다시 시작하게 되고 8과 비교했을 때 8이 더 크므로 8 앞의 1개를 더 제거 한다.
   4. 이제 제거할 숫자가 없으므로 2 부터 시작해서 8, 3을 차례로 stack에 넣는다.
5. stack에 있는 문자를 join으로 묶어서 반환하면 끝!

느낀점

• 다른 프로그래머스 2레벨 문제를 풀다보니 실력이 늘었다.
• 하지만 겸손 또 겸손 이제 2레벨 다 풀면 3레벨을 다 풀어야 한다.