BOJ 2812 - 크게 만들기

www.acmicpc.net/problem/2812

2812번: 크게 만들기

 

이 문제는 적절한 자료구조를 잘 선택해야 풀 수 있는 문제이다.

이 문제에선 스택을 사용해서 문자들을 하나씩 처리해주는게 좋다

 

입력으로 들어오는 숫자가 최대 50만 자릿수를 가지므로 문자열로 만들어주고 

문자를 앞에서부터 끝까지 돌면서,

지워야할 갯수 k 가 0 보다 큰경우, 스택이 비어있지 않은경우, 스택의 맨 윗값이 현재 문자보다 작은 경우를 동시에 만족하는 경우, 스택에서 하나씩 빼내면서 k 를 줄인다.

그리고 난 후 문자를 하나씩 추가해서 스택에 넣는다.

for (int i = 0; i < str.length(); ++i) {
    while(k && !st.empty() && st.top() < str[i]) {
        st.pop();
        k--;
    }
    st.push(str[i]);
}

 

주의할점은 k 개 만큼 지워지지 않았을때다.

예를들면, N = 3, K = 2, 321 이 주어졌을때 

위 코드대로 하면, 321 이 스택에 전부 들어간다. 

 

그러므로 위 반복문을 빠져나오면서 k 개 만큼 스택에서 빼야한다.

while(k--) st.pop();

 

스택은 LIFO 구조를 가지므로 스택에 저장된 값 그대로 출력하면 역으로 출력하게 된다.

그러므로, 하나씩 빼면서 문자열로 추가해주고 이를 역순으로 돌리면 된다.

 

 

(좀 더 다른데 찾아보니 이렇게 출력할바에, 차라리 그냥 deque 를 쓰는게 낫다)

 

 

- c++

#include <algorithm>
#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
 
int n, k;
string str;
stack<char> st;
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n >> k;
    cin >> str;
    
    for (int i = 0; i < str.length(); ++i) {
        while(k && !st.empty() && st.top() < str[i]) {
            st.pop();
            k--;
        }
        st.push(str[i]);
    }
    
    while(k--) st.pop();
    
    string answer;
    while(!st.empty()) {
        answer.push_back(st.top());
        st.pop();
    }
    
    reverse(answer.begin(), answer.end());
    cout << answer;
    
    return 0;
}