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

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

프로그래머스

풀이

주어진 number의 범위가 1,000,000 이기 때문에 1번의 loop로 해결해야 하는 문제입니다.

 

따라서, 스택을 사용해 greedy하게 문제를 해결할 수 있습니다.

알고리즘은 다음과 같습니다.

 

1. stack의 가장 위에 존재하는 수를 현재 수와 비교합니다.

2. 현재 수가 top보다 크고 k가 0보다 크다면(삭제할 수가 남았다면), 더 이상 비교할 수가 없을 때까지 1번을 반복하며 stack의 가장 위의 수를 삭제합니다.

3. 현재 수보다 작거나 같은 수는 모두 push 해줍니다.

4. 반복할 수가 없다면 현재 수를 push하고 idx를 늘려줍니다.

5. stack에서 숫자를 빼낸 후, 삭제 되지 않은 경우 ( "21", 1 의 경우 "21"이 출력됨)를 위해, 출력해야 하는 숫자 n개 만큼을 substr함수를 사용해 answer에 대입합니다.

 

리뷰

변수 범위에 의해 dfs 풀이는 시간 초과가 되는 문제입니다.

20번에서 오답이 난다면 경계조건에 존재하는 테스트 케이스를 만들어 테스트 해볼 필요가 있습니다.

 

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

using namespace std;

string solution(string number, int k) {
    string answer = "";
    int n = number.size()-k;
    string s;
    stack<char> stk;
    stk.push(number[0]);
    int idx = 1;
    /*
        stack top과 비교
        현재가 더 클 경우 pop & k-- & 현재 수 push
        현재가 더 작거나 같은 경우 push
        k가 0이 될때 종료 및 리버스 출력
    */
    while (idx < number.size()) {
        char c = stk.top();
        if (number[idx] > c && k > 0) {
            stk.pop();
            // cout << "pop: " << c << endl;
            k--;
        }
        else {
            stk.push(number[idx]);
            // cout << "push: " << number[idx] << endl;
            idx++;
        }
        
        if (stk.empty()) {
            stk.push(number[idx]);
            // cout << "empty push: " << number[idx] << endl;
            idx++;
        }
    }
    
    while (!stk.empty()) {
        s += stk.top();
        stk.pop();
    }
    reverse(s.begin(), s.end());
    answer = s.substr(0, n); 
    return answer;
}