[프로그래머스] (Greedy) 큰 수 만들기 (C++)

큰 수 만들기(Level2)

문제

전체 문제 보기

코딩테스트 연습 - 큰 수 만들기

접근법

그리디란 부분적인 최적의 해가 전체적인 최적의 해가 되는 알고리즘을 말한다. 그래서 먼저 부분적인 최적의 해를 정의해 보고, 부분적인 최적의 해가 전체적인 최적의 해가 될 수 있다면 그리디로 풀 수 있다. 그래서 이문제를 풀기 위해 먼저 부분적인 최적의 해를 정해보자.

 

이 문제에서 구해야 하는 값은 number 라는 수에서 k개의 숫자를 제거했을 때 가장 큰 수이다. 큰 수를 만들기 위해서는 앞에 있는 숫자를 가장 크게 만들어 주면 된다. 앞에 있는 숫자를 가장 크게 만들기 위해서 우리는 어떤 수를 삭제해야 할지 기준을 마련해야 한다. 이 기준이 부분적인 최적의 해가 될 것이다. 문제를 쉽게 풀기 위해서 Stack 개념을 활용한다. (이 문제를 푸는 과정에서 Stack에 저장된 원소를 순차적으로 조회하는 기능이 필요한데, std::stack은 저장된 원소를 순차적으로 조회하는 기능이 없기 때문에 사용할 수 없기 때문에 문자열을 그냥 stack처럼 사용한다.)

 

설명을 위해서 문제의 예시 2번째 값을 활용한다.

number : 1231234 / k : 3

• 먼저 첫 번째 수를 answer 문자열에 push 한다.

• 큰 수가 되기 위해서는 앞에 있는 숫자가 커야 한다. 그러기 위해서는 앞에 있는 작은 수를 버려야 한다. 1과 2 중에서 1이 더 작기 때문에 1을 pop 하고 2를 answer 문자열 스택에 push 한다.
• 1을 버렸기 때문에 k 값은 1 감소시킨다.

• 다음으로 2와 3을 비교한다. 2가 더 작기 때문에 2를 pop 하고 3을 answer 문자열 스택에 push 한다.
• 2를 버렸기 때문에 k 값은 1 감소시킨다.

• 다음으로 3과 1을 비교한다. 이번에는 1이 작기 때문에 그대로 answer 스택에 push 한다.

• 이번에는 answer 스택의 1과 number의 2를 비교한다. 1이 더 작기 때문에 1을 pop 하고 answer 스택에 2를 push 한다.
• 1을 버렸기 때문에 k 값을 1 감소시킨다.

• 이제 k 값이 0이다. 즉 더 이상 버릴 수 없기 때문에 남은 수 들을 모두 push 해준다.

최종적으로 가장 큰 수 3234가 answer에 남아 있는 것을 확인할 수 있다.

 

정리하면 이번 그리디 알고리즘의 부분적인 최적의 해는 앞자리에 있는 작은 수를 버린다 이고, 이를 k가 0이 될 때까지 반복하면 된다.

 

단, 이 방식에는 예외가 한 가지 있다. 만약 테스트 12번만 오류가 난다면 다음 과같은 예외를 고려해야 한다.

number : 111111 / k : 2

이렇게 같은 수가 많아서 버릴 값이 없거나 부족한 경우 반복문을 마치고 남은 k만큼 맨 뒤의 수를 버려주는 작업을 별도로 진행해야 한다.  

구현

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string answer = "";

    // 초기값을 push
    answer.push_back(number[0]);

    for(int i = 1; i < number.length(); i++)
    {
        char num = number[i];

        while(!answer.empty() && k > 0 && answer.back() < num)
        {
            answer.pop_back();
            k--;
        }
        answer.push_back(num);
    }

    // 아직 삭제해야할 수가 남았다면 뒤에서부터 삭제해준다.
    while(k > 0)
    {
        answer.pop_back();
        k--;
    }

    return answer;
}