[BOJ 2812] 크게 만들기

BOJ 2812 크게 만들기

유형

• 스택

풀이

예전에 풀어본 문제였지만 바로 풀이가 떠오르지는 않았다. 나름에 알고리즘을 만들어보려고 했지만 예외가 너무 많았고 유형을 보니 스택을 사용해서 푸는 문제였다.

스택을 사용하면 풀이가 간단하게 끝이 난다. 입력된 값의 처음부터 순회하면서 현재값보다 스택의 있는 값이 작거나 같을 때까지 스택을 비우고 그 후 스택에 채워넣는다.

스택을 k번 비울 때까지 위 과정을 반복하고 스택에 있는 값과 아직 순회하지 않은 입력값을 합치면 정답을 얻을 수 있다.

N <= 500000이기 때문에 string으로 처리해야한다.

예외적인 상황은 입력값이 내림차순으로 정렬되어있거나 부분적으로 그런부분이 있으면 스택을 k번 비우기 전에 순회가 끝날 수도 있다. 그런 경우에는 구한 정답에서 뒤에서 남은 k만큼 버리고 출력하면 된다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;
int n, k;
string str;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);

	cin >> n >> k >> str;

	stack<char> s;
	s.push(str[0]);
	int i = 1;
	while (i < n && k > 0) {
		// 현재값보다 스택에 있는 값이 작으면 스택에서 비우기
		while (!s.empty() && s.top() < str[i] && k > 0) {
			s.pop();
			k--;
		}
		s.push(str[i]);
		i++;
	}
	string temp = "";
	while (!s.empty()) {
		temp += s.top();
		s.pop();
	}

	reverse(temp.begin(), temp.end());
	// k가 남았으면 뒤에서 k개 만큼 버리기
	if (k != 0) temp = temp.substr(0, temp.size() - k);

	cout << temp << str.substr(i);

	return 0;
}