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

문제

https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

풀이

LG 기출이랑 비슷하다.

#17298과 비슷하게 stack + 그리디..
하지만 값 출력하기 편하게 stack이 아닌 deque를 사용했다.
문자열의 이전 값들이 더 작으면 pop을 계속 해주고 k값을 감소한다.

72%정도에서 계속 틀렸습니다가 떴는데, 마지막 출력하는 과정에서 dq.size()-k을 꼭 해줘야했다.
그냥 auto써서 dq다출력하는게 아니라.. k를 빼줘야하는 이유는 뭘까..?

5 1
76543

의 예시를 생각해보자. k가 0보다 크고 dq도 비어있지 않지만 i번째 수가 i-1번째 수보다 항상 크다. 
그래서 pop할게 아무것도 없고, 계속 push만 한다.
결국 dq안에 있는 마지막 숫자가 76543일 것이다. 이러면 k=1이니까 3을 제외하고 7654를 출력해야한다.
그래서 dq.size()-k를 꼭 해줘야한다. 

만약, 

4 2
9241

의 예시라면, 2와 1이 pop되므로 마지막에 k가 0일 것이다.
그래서 dq안에 있는 것을 전부 출력하면 된다. 

단순히 예제 입출력만 고려하는 것이 아니라, 사고의 확장을 통해 k가 0이 아닌 경우를 따져줘야했다.

코드

#include<bits/stdc++.h>
using namespace std;

int n, k;
string num;
deque <char> dq;


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

	cin >> n >> k;
	int kk = k;
	cin >> num;
	for (int i = 0; i < n; i++) {
		while (k >0 && !dq.empty() && dq.back() < num[i]) {
			dq.pop_back();
			k--;
		}
		dq.push_back(num[i]);
	
	}
	for (int i = 0; i < dq.size()-k; i++) {
		cout << dq[i];
	}
}