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

프로그래머스의 큰 수 만들기(Lv2) 문제이다.

[ 문제풀이 ]

1) 본인은 이 문제를 스택을 이용해서 한번 생각해 보았다.

   전체적인 과정은 다음과 같다.

   1. 전체 숫자를 탐색하면서, 가장 앞에 숫자부터 스택에 넣을 수 있는지 판단한다.

   2. 여기서 "판단한다" 라는 것은

     1) 스택의 가장 위에 있는 값이 현재 넣으려는 숫자보다 더 크다면 그대로 넣어준다.

     2) 스택의 가장 위에 있는 값이 현재 넣으려는 숫자보다 작다면, 현재 넣으려는 숫자보다 크거나 같은

       숫자가 나올 때 까지, 스택의 값을 빼준 후에 넣어준다.

   이러한 과정인데 무슨 말인지 하나도 모르겠으니 예시를 통해서 알아보자.

   예제입력으로 주어진 "1924"의 경우를 생각해보자.

   "1924"중 2개의 갯수를 빼서 가장 큰 숫자를 만들어야 한다.

   1. '1'을 스택에 넣을 수 있는지 판단한다.

      이 경우에는 아직 스택에 아무런 값도 없으므로 그대로 넣어준다.

   2. '9'를 스택에 넣을 수 있는지 판단한다.

      스택의 top에 있는 값이 '1' 이므로, '1'을 빼준 후, 9를 넣어준다. (제거한 횟수 : 1)

   3. '2'를 스택에 넣을 수 있는지 판단한다.

      스택의 top에 있는 값이 '9'이므로, 현재 넣으려는 숫자보다 스택의 가장 위에 있는 값이 더 큰 경우이므로

      그대로 넣어준다.

      ( 현재 스택의 상태 : [ 2, 9 ] )

   4. '4'를 스택에 넣을 수 있는지 판단한다.

     스택의 top에 있는 값이 '2' 이므로, 현재 넣으려는 숫자보다 작기 때문에 값을 빼준다. (제거한 횟수 : 2)

     ( 현재 스택의 상태 : [ 9 ] )

     스택의 top에 있는 값이 '9'이므로, 현재 넣으려는 숫자보다 크기 때문에 그대로 넣어준다.

     ( 현재 스택의 상태 : [ 4 ] )

   이렇게 계산을 끝내면 스택에 [ 4 , 9 ] 가 존재하게 된다. 이 후 스택을 역으로 출력을 해주면 된다.

   하지만, 이렇게만 생각을 하면 안된다. 예를 들어서 "9876" 에서 2개의 문자를 제거해서 최댓값을 만드는 경우를

   생각해보자.

   처음에 '9'가 들어가고, '8'이 들어갈 때, 8보다는 9가 더 크기 때문에 그냥 넣어주므로, [ 8, 9 ] 가 된다.

   이 후, 7, 6을 순서대로 값을 넣어주더라도 제거되는 숫자 하나 없이, [ 9, 8, 7, 6 ] 이 스택에 저장되어 질 것이다.

   이렇게 제거가 되지 않는 경우는 물론, 제거가 몇개 되더라도 문제에서 주어진 K번 만큼 제거하지 못하는 경우가

   발생한다.

   하지만, 위의 계산대로라면 스택에는 큰 값일수록 가장 아래쪽에, 작은 값일수록 top()쪽에 가깝게 위치하고 있을 것이다.

   따라서 남은 횟수만큼 스택에서 값을 빼주면 된다.

   "9876"에서 계산을 끝냈더니 스택에 [ 6 , 7, 8, 9 ] 가 존재했고, 아직 문자를 제거한 횟수가 0회 이므로,

   2번만큼 제거하기 위해서 스택에서 2번만큼만 pop연산을 하게 되면, [ 8, 9 ] 가 남게 되고, 이를 역순으로 출력하면

   "98" 이라는 결과를 얻을 수 있다.

[ 소스코드 ]

#include<string>
#include<stack>
 
using namespace std;
 
string solution(string S, int K)
{
    string Answer = "";
    stack<char> Stack;
    int Remove_Cnt = 0;
    int Answer_Size = S.length() - K;
 
    for (int i = 0; i < S.length(); i++)
    {
        char Num = S[i];
        while (Stack.empty() == 0 && Remove_Cnt < K)
        {
            char TopNum = Stack.top();
            if (TopNum < Num)
            {
                Stack.pop();
                Remove_Cnt++;
            }
            else break;
        }
        Stack.push(Num);
    }
 
    while (Answer_Size != Stack.size()) Stack.pop();
    stack<char> Temp;
    while (Stack.empty() == 0)
    {
        Temp.push(Stack.top());
        Stack.pop();
    }
    while (Temp.empty() == 0)
    {
        Answer = Answer + Temp.top();
        Temp.pop();
    }
    return Answer;
}

cs