Programmers Level 2: 큰 수 만들기(C++)

https://programmers.co.kr/learn/courses/30/lessons/42883#

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

풀이법

1) 스택을 이용하여서 문제를 해결하였다.

2) 스택이 비어있는 경우는 해당 index의 값을 넣어 주었다.

3) 들어갈 수 있는 값의 개수를 지정하였고, 스택의 맨 위의 값보다 현재의 값이 큰 경우, 스택을 지속적으로 비워 주었다. 이때 넣을 수 있는 남은 값과 스택의 크기를 합하여 값의 개수보다 큰 경우만 반복을 지속하였다.

        if(st.top()<number[i])//현재 값보다 작으면 계속 뺀다.
        {
            while(!st.empty() && st.size()+j>k && st.top()<number[i])
            {
                st.pop();
            }
            st.push(number[i]);
        }

4) 여기까지만 진행하면 test case 12 번에서 오류가 난다. 대표적인 예시로 (987654321 , 2) / (77777,2) 와 같이 지속적으로 감소하는 값이 들어오게되면 해당 로직으로는 stack의 크기가 들어갈 수 있는 값의 개수보다 커지게 된다.

5) 이 경우를 대비하여 stack의 크기가 들어갈 수 있는 값의 크기보다 클 경우 마지막 값들을 pop 시켜서 크기를 맞추어 주었다.

#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

string solution(string number, int k) {
    string answer = "";
    stack<char> st;
    int t=k;
    k=number.size()-k;//총 들어가야하는 개수
    for(int i=0; i<number.size();i++)
    {
        int j=number.size()-i;//더 넣을 수 있는 예비 개수
        if(st.empty())
        {
            st.push(number[i]);
            continue;
        }
        if(st.top()<number[i])//현재 값보다 작으면 계속 뺀다.
        {
            while(!st.empty() && st.size()+j>k && st.top()<number[i])
            {
                st.pop();
            }
            st.push(number[i]);
        }
        else// 같거나 클 경우는 계속 넣는다.
        {
            st.push(number[i]);
        }  
    }
    if(st.size()>k)
    {
        while(st.size()!=k)
        {
            st.pop();
        }
    }
    while(!st.empty())
    {
        answer+=st.top();
        st.pop();
    }
    reverse(answer.begin(),answer.end());
    return answer;
}