[백준] 2812-크게 만들기(C++)

문제링크: https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

수학적인 관점에서 생각해봐야 하는 그리디 문제였습니다. 

 

접근방식

 

1. 처음에는 단순히 arr[0], arr[1]만 비교해주고 값을 지워가면 되는 것으로 이해함

2. 근데 예외가 분명히 존재함

7 3

7654321

결과값은 7654

3. 뒤에 있는 값들도 함께 고려해야한다는 것을 알게됨

4. dequeue에 값들을 저장하고  뒤에 있는 값보다 작은 경우에는 dequeue에서 제외해주는 형태로 구현하자!

 

문제풀이 

 

1. 문자열의 이전 값(deque에 저장된) 들이 더 작다면 pop을 계속 시행, k값 감소

2. deque에 해당 문자열 삽입 

3. 출력할 때는 deq.size() - k만큼 출력

 

아래는 정답 코드

#include <iostream>
#include <string>
#include <deque>
using namespace std;

int n, k;
string val;
deque <char> deq;
int main() {
	iostream::sync_with_stdio(0);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	cin >> val;

	for (int i = 0; i < val.length(); i++) {

		while (k && !deq.empty() && deq.back() < val[i]) {
			deq.pop_back();
			k--;
		}
		deq.push_back(val[i]);
	}


	for (int i = 0; i < deq.size() - k; i++) 
		cout << deq[i];
	
	cout << "\n";

	return 0;
}