Programmers - 큰 수 만들기

stack을 사용하는 문제이다. 처음에 접근했던 방법은 greedy라는 단어만 보고 입력된 수로 가능한 조합을 하는 것이였다. 가능한 수로 조합을 진행할 때, 입력된 k만큼 입력된 numbers에서 가장 작은 수부터 k개의 원소를 가진 배열을 만들었다. 이 배열에 포함되는 수를 제외하면서 새로운 배열의 조합을 만들어 나갔는데, 예외 경우를 모두 잡을 수 없었고 time Complexity가 상당히 높다.

질문하기를 참고해서 stack을 이용해야 된다는 힌트를 얻었다. 바로바로 생각이 안나니 포스팅을 통해 정리를 해보기로 하였다.

function solution(number, k) {
    /**
     *  stack을 이용한 풀이방법
     *  각 원소별로 비교를 해주는데, 현재 뽑은 원소가 stack안에 저장되어있는 값들과 비교
     *  현재 원소 vs stack[top] 을 진행해준다.
     * 
     *  ! 스택을 사용하기 때문에 index는 지켜진다. 
     */
    let stack = [];
    // 각 원소마다 진행 !
    number.split('').forEach((element) => {
        /**
         *  1. 무조건 stack에 push를 한다.
         *  2. while loop {
         *          element와 stack[top] 비교
         *          stack에서 빼는 순간(=pop()) -> k -= 1;
         *     }
         *  3. k를 모두 소진했다면 그냥 push
         */
        while (k > 0 && stack[stack.length - 1] < element) {
            stack.pop(); k -= 1;
        }
        stack.push(element);
    });
    /**
     *  k 개의 숫자를 제거했다면 stack은 그대로 두고 
     *  number.length - k 만큼 반환하기
     *  k가 남아있는 경우에는 뒤에서 제거
     *  ex) [1,9,2,2], 2 -> 92
     */
    stack.splice(stack.length - k, k);

    return stack.join('');
}

주석에 작성한 것과 같이, stack을 이용해서 각 원소마다 while문을 통해서 stack의 top과 비교과정을 거쳤다.

1. 각 원소별로 먼저 stack에 push를 해준다.
2. while문을 통해서 각 원소와 stack의 top과 비교를 해준다.
3. 완성된 stack에서 *k가 남아있다면 뒤에서부터 k만큼 제거해준다.