*[백준][2812] 크게 만들기

www.acmicpc.net/problem/2812

2812번: 크게 만들기

문제

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

 

해결 방법

1. 덱을 이용하여 양끝에서 삽입, 삭제가 가능한 구조를 이용하였다.

2. 덱에 가장 뒤의 숫자보다 현재 숫자가 더 크다면 가장 뒤에 숫자를 삭제하고, 현재 숫자를 넣어주었다.

3. 마지막 출력 시 현재 덱의 사이즈 - K 만큼 돌려야 내림차순으로 이루어진 숫자에 정답을 구 할 수 있다. 2번의 조건에서 내림차순의 경우 해당사항이 없어진다.

 

소스코드

#include <stdio.h>
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main()
{
	deque<char> dq;
	//deque란  삽입과 삭제가 양쪽 끝에서 모드 가능한 자료구조
	//push_back, push_front
	int N, K;
	scanf("%d %d", &N, &K);
	string number;
	cin >> number;
	for (int i = 0; i < N; i++) {
		while (K > 0 && !dq.empty() && dq.back() < number[i]) {
			dq.pop_back();
			K--;
		}
		dq.push_back(number[i]);
	}
	for (int i = 0; i < dq.size() - K; i++) {
		printf("%c", dq[i]);
	}
	printf("\n");
	return 0;
}

결과