C++ / 백준 / 2812 / 크게 만들기

문제

 

https://acmicpc.net/problem/2812

2812번: 크게 만들기

문제풀이

 

우선순위큐로도 풀 수 있는 거 같은데 스택이 코드가 더 간단해 보여서 스택으로 풀었다.

이 문제는 뒤로 가면서 큰 숫자를 발견하면 이전 숫자를 지우기만 하면 된다.

 

스택을 이용해 숫자를 push 하고, 큰 수가 나온다면, 스택이 비거나 스택의 top과 같을 때까지 pop을 하면 된다.

또는 지운 개수가 K개까지만 반복하면 된다.

 

입력받은 문자열을 모두 탐색했으면, K개를 안 지운 경우도 있을 수 있으니, while문을 이용해 추가로 지워준다.

스택에는 똑바로 쌓여있지만 후입선출이므로, string으로 옮기고 reverse 하여 답을 출력한다.

 

코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N(0), K(0), idx(0), cnt(0);
	string num(""), answer("");
	stack<char>s;
	cin >> N >> K >> num;

	for (idx = 0; idx < N; ++idx) {		
		while (cnt < K && !s.empty() && s.top() < num[idx]) {			
			s.pop();
			cnt++;
		}
		s.push(num[idx]);		
	}
	while (cnt < K) {
		s.pop();
		++cnt;
	}

	while (!s.empty()) {
		answer += s.top();
		s.pop();
	}

	reverse(answer.begin(), answer.end());
	cout << answer;
}