프로그래머스 - 큰 수 만들기

✨ Lv. 2 - 큰 수 만들기

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42883

문제 설명

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

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

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

제한사항

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

풀이 코드 + 설명

숫자를 제거하고 재배치하여 최대가 되는 숫자를 찾는 것이 아닌, 특정 위치의 숫자를 k개 제거하여 만들 수 있는 가장 큰 숫자를 구하는 것이 목적입니다.

따라서 k개를 제거하며 큰 숫자들만 나열할 수 있도록 아래와 같이 풀이하였습니다.

• 결과를 담을 배열(스택)을 생성합니다.
• number를 순회하며, 아래를 반복합니다.
  - 배열이 비어있는 경우, 현재 값을 push 합니다.
  - 배열 상단에 있는 값이 현재 값보다 작다면, 작은 값들을 pop합니다.
  - 배열 상단에 있는 값이 현재 값보다 크다면, 현재 값을 push 합니다.
  - 단, 더 이상 숫자를 제거할 수 없을 경우, 나머지를 전부 push 합니다.

이를 바탕으로 작성한 코드는 아래와 같습니다.

function solution(number, k) {
    let result = [];
    
    [...number].map((v) => Number(v)).forEach((v, i) => {
        while(true) {
            if(result.length === 0) {
                result.push(v);
                break;
            }
            else if(k + result.length !== i && result.at(-1) < v) result.pop();
            else {
                if(result.length === number.length - k) break;
                result.push(v);
                break;
            }
            
        }
    });
    
    return result.join('');
}

위 코드를 아래와 같이 작성하여 pop한 숫자의 개수를 기준으로 pop과 push를 진행하여 해결할 수 있습니다. 마지막의 slice는 이미 주어진 숫자가 전부 내림차순인 경우, 전체가 그대로 return 되기 때문에 해당 케이스를 처리하기 위한 slice 입니다.

function solution(number, k) {
    let result = [];
    let counter = 0;
    
    [...number].map((v) => Number(v)).every((v, i) => {
        if(result.length === 0) result.push(v);
        else {
            while(result.at(-1) < v) {
                result.pop();
                counter++;
            
                if(counter === k) {
                    result.push(number.slice(i));
                    return false;
                }
                if(result.length === 0) break;
            }
        result.push(v);
        }
        return true;
    });
    
    return result.join('').slice(0, number.length - k);
}