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

https://school.programmers.co.kr/learn/courses/30/lessons/42883?language=cpp# 

프로그래머스

처음에는 순열을 이용해서 모든 경우의 수를 다 탐색해가며 최대 숫자를 찾으려고 했다. 근데 입력으로 주어지는 number 길이가 최대 백만이라 아마 시간초과가 날 것같아서 다른 풀이를 탐색했고, 약간의 구글링을 통해 얻은 아이디어로 아래와 같이 구현하였다.

 

먼저  number 가 주어지면 stack 에 차곡차곡 넣는다.

예를 들어 number = 1924, k  = 2 라고 가정하자.

number 을 순회하며 각 원소를 stack 에 넣을지 말지를 결정한다.

맨 처음에는 stack 이 비워져있으므로 넣는다.

-> stack : { 1 }

그리고  k > 0 이고 i < number.size() 이므로 다음 원소인 9 를 바라봤을 때 현재 stack 의 top 보다 크다.

그러므로 stack.top() 이 9 보다 클 때까지 pop 을 하며, k 를 하나씩 줄인다.

-> stack : { } , k = 1

스택이 비워졌다. 그러면 그냥 넣는다.

-> stack : { 9 }, k =1

다음 수를 탐색한다. 2 는 9 보다 작으므로 그냥 넣는다.

stack : { 9 , 2}, k = 1

다음 수를 보니까 4인데 stack.top() 인 2 보다 크다.

pop 을 수행하고 k 를 하나 줄인다.

그러니까 k = 0 이 되어버렸다. 만약 이 시점에서 모든 원소를 탐색하지 않았다면, 뒷 원소들은

차례대로 차곡차곡 스택에 push 해준다. 혹은 모든 원소를 탐색했는데 k 가 0 이 아니라면

k 의 개수만큼 stack 을 pop 해준다.

 

위 과정을 거친 다음 stack 을 answer 로 옮겨주면 완성.

 

[C++]

#include <string>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    stack<char> st;
    
    int i = 0;
    for(i = 0 ; i < number.size(); i++)
    {
        if(k==0) break;
        if(st.empty()){
            st.push(number[i]);
            continue;
        }
        else
        {
            while(!st.empty()&&st.top() < number[i] && k)
            {
                st.pop();
                k--;
            }
            st.push(number[i]);
            continue;
        }
    }
    while(i!=number.size())
        st.push(number[i++]);
    
    while(k>0 && !st.empty())
    {
        st.pop();
        k--;
    }
    
    
    while(!st.empty())
    {
        answer.push_back(st.top());
        st.pop();
    }
    reverse(answer.begin(), answer.end());
    return answer;
}