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

1. 문제

문제 링크

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

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

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

제한 조건

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

입출력 예

number	k	n
"1924"	2	"94"
"1231234"	3	"3324"
"4177252841"	4	"775841"

2. 풀이

k개를 제거하겠다는 말은 n - k개를 남기겠다는 의미와 동일합니다.
이 문제는 앞자리부터 순차적으로 탐색하며
가장 큰 수를 만들 수 있도록 n - k개의 문자를 선택하는 문제로 생각할 수 있습니다.

이런 문제는 스택을 활용해서 많이 풀게 됩니다.
스택은 LIFO정책, 즉 마지막에 들어간 원소가 먼저 나오는 정책을 따르고 있습니다.
이 문제에서 스택을 어떻게 활용할 수 있을까요?

일단 큰 수를 만드려면 큰 숫자를 가능한 자릿수가 큰 쪽으로 옮겨줘야 합니다.
"321923"를 예로 들어보죠.
이 중에 가장 큰 숫자는 "9" 입니다.
"9"를 가장 왼쪽으로 붙여줘야 큰 숫자를 만들 수 있습니다.
k가 1일 때 "32923"
k가 2일 때 "3923"
k가 3일 때 "923"

규칙이 보이시나요?
숫자 "9"를 가장 왼쪽에 붙여주기 위해서는
이전에 나온 수와 대소 비교를 하고
현재 나온 숫자("9")가 크다면 이전에 나온 숫자를 제거하고 있습니다.

이 때 이전의 나온 숫자를 스택에 저장하게 됩니다.
왜 하필 큐도 아니고 스택에 저장하는 이유는
스택은 LIFO정책을 따르기 때문에 스택의 맨 위의 요소는
이전에 나온 숫자중에서 가장 작은 숫자가 저장되어 있기 때문입니다.

그렇기 때문에 스택에는 큰 숫자일 수록 밑에 있도록 저장하게끔 하면
스택에는 만들 수 있는 가장 큰 숫자가 남아있게 됩니다.

3. 전체 코드

function solution(number, k) {
    const stack = [];

    [...number].forEach(num => {
        // stack에 원소가 있으면서 k가 양수일 때
        while (stack.length && k) {
            // 스택의 맨 위의 원소가 현재 숫자보다 크거나 같다면 break
            if (stack[stack.length - 1] >= num) break;

            stack.pop();
            k--;
        }

        // 스택에 숫자 넣기
        stack.push(num);
    });

    // 나머지 숫자들을 스택에서 빼내기
    while (k--) stack.pop();

    return stack.reduce((m, num) => m += num, '');
}