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

목표 : 그리디에 대해 간단히 알아보고 이를 이용하여 문제를 풀이해보자

문제 설명

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

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

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

제한 조건

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

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

문제 풀이

Greedy 탐욕법

이 문제는 그리디 알고리즘과 스택을 이용해서 풀 수 있습니다.

그리디 알고리즘은 매 순간 가장 최선의 선택을 하는 알고리즘을 의미합니다. 그리디로 도출한 값은 가장 최적의 답이라고 확신할 수는 없지만, 가장 최선인 값이기도 합니다.

그리디 알고리즘의 가장 대표적인 예시로는 유명한 마시멜로 시험이 있습니다. 그리디는 현재 상황에서 가장 최선의 선택인 ‘지금 당장 마시멜로 1개를 먹는다’를 보장해 주지만, ‘기다렸다가 마시멜로 2개를 먹는다’라는 최적의 선택을 보장해주진 못합니다.

풀이과정

자, 이제 그리디와 스택을 이용하여 문제를 풀어봅시다.

그리디는 숫자를 제거할지 말지를 선택하는 기준으로, 스택은 제거하지 않을 숫자를 담아두는 저장 용도로 사용됩니다.

먼저, numbers를 순회하면서 stack에 각 숫자를 push줍니다.

push를 한 후 다음의 반복문을 돌려줍니다.

조건

1. 스택의 가장 마지막에 있는 값(push한 숫자의 값)이 바로 앞의 값보다 크고
2. 제외할 수 있는 횟수(k)가 남아있다면

행동

1. 스택 마지막 값과 마지막 앞의 값을 바꿔줍니다.
2. 스택의 마지막 값을 제거합니다.

상술한 반복문을 통해 제거 할 수 있는 한 가장 큰 자연수들이 스택 앞에 오도록 할 수 있습니다. 아주 정확할 순 없지만, 매 순회에서 가장 최선의 선택을 하는 것, 바로 그리디의 핵심입니다.

엣지 케이스

아직 제거해야 할 횟수(k)가 남아있을 수 있습니다. 이러한 엣지 케이스는 number에서 내림차순으로 정렬되지 않은 수가 k보다 적을 때 발생합니다. number로 ‘4321’, ‘54312’ 등이 주어졌을 때 그러한 경우이죠.

이럴 땐 남은 횟수 만큼 스택의 요소들을 제거해주면 됩니다.

코드

const solution = (number, k) => {
        // 제거하지 않을 숫자를 담아둘 저장소
    const stack = [];

    // numbers를 순회합니다.
    number.split('').forEach(str => {
                // 스택의 가장 마지막에 현재의 값 push.
        stack.push(str * 1);
                // 반복문 실행 (상단의 풀이과정 참조)
        while(stack[stack.length - 1] > stack[stack.length - 2] && !!k) {
            k -= 1;
            stack[stack.length - 2] = stack[stack.length - 1];
            stack.pop();
        }
    });

    let answer = stack.join('');
        // 엣지 : 아직 제거해야할 횟수가 남아있다면, 남은 횟수만큼 맨 뒤의 숫자를 제거해줍니다.
    if(!!k) answer = answer.slice(0, -k);
    return answer;
}