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

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

숫자의 순서를 유지하면서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하는 문제이다.

numbers 길이에서 k개를 선택하는 모든 경우의 수를 탐색하면 TLE가 발생할 것이 분명하므로 더 간단한 풀이를 찾아야 한다.

 

어떻게 해결하면 좋을까 하다가 이런 생각이 들었다.

"만약, 앞에 있는 수가 현재 수보다 작으면 앞에 있는 수를 제거해서 한자리씩 앞으로 당기는 것이 더 큰 수를 구하는 방법이지 않을까?"

예를 들어, 17725.... 가 있다고 했을 때 7은 1보다 크고, 1을 제거해서 7을 앞당기는 것이 가장 큰 수를 만드는데 유리하다.

 

해서, 숫자의 각 자리를 순회하면서 스택에 넣되, 스택에 이미 들어있는 수 중에서 현재 스택에 넣으려고 하는 수보다 작은 수가 있으면 이를 제거한다. 물론, 제거하는 숫자의 총 개수는 cnt 이하이어야 한다.

 

해당 과정을 모두 반복한 후 스택에 남아있는 숫자들로 문자열을 만들자.

문자열의 길이가 numbers.size() - k를 넘지 않도록 substr() 결과를 리턴하면 정답이다.

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cctype>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

string solution(string number, int k) {
    
    stack<char> st;
    int cnt = 0;
    for (auto x : number) {
        while (!st.empty() && cnt < k && st.top() < x) {
            st.pop();
            cnt++;
        }
        st.push(x);
    }
    
    string ans = "";
    while (!st.empty()) {
        ans = st.top() + ans;
        st.pop();
    }
    
    return ans.substr(0, number.size()-k);
}