백준 2812번 - 크게만들기 (C++,deque)

백준 2812번

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

2812번: 크게 만들기

문제설명

 

 

 

 

문제설명

N자리 숫자를 입력받고 K개를 지워 가장 큰수를 구하는 문제 (숫자의 위치를 바꿀 수 없음)

 

 

접근

처음 접근할 때에는 문제를 잘못 이해하여 입력받은 숫자의 순서를 바꿔서 정렬로 풀었다. (결과: 실패)

틀린이유를 찾다가 고민 끝에 문제를 제대로 이해하여 deque를 사용하여 구현

 

 

코드

코드
// 헤더파일은 여러가지 문제를 풀기 편하게 그냥 고정해둠,,

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>

using namespace std;

char str[500001] = { 0, };

bool desc(int a, int b)
{
	return a > b;
}
int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	

	int N, K; // N = 숫자의 자리수, K = 지울 숫자의 개수
	deque<char> dq;


	cin >> N >> K; // 입력받기
	cin >> str;


	for (int i = 0; i < N;i++)
	{
		while (K && !dq.empty() && dq.back() < str[i]) // 큐가 비어있지않고, K(빼야할 횟수)가 0이아니며, 덱의back이 비교하는 숫자보다 작으면
													//pop back후 k를 1감소 아니면 pushback
		{
			dq.pop_back();
			K--;
		}
		dq.push_back(str[i]);
	}


	for (int i = 0; i <dq.size()-K ; i++) //k를 감소하는 갯수가 무조건 0 까지 줄지 않음, 예외가 존재
	{
		cout << dq[i];
	}
	cout << endl;
	

	return 0;

}

 

코드설명

1. 우선 N,K 와 N자리 숫자를 문자로 입력을 받는다.

2. N자리 숫자만큼 for문을 반복한다.

3. for문 안에서의 가장 큰값을 위해 while문을 통해 deque가 비어있지않고, K(빼야하는 횟수)가 0이아니며, q의 마지막 숫자가 비교하려는 숫자보다 작으면 K를 1감소시키고 숫자를 교체한다.

그렇지 않은경우, pushback을통해 deque에 숫자를 집어 넣는다.

4. K가 무조건 0이 되는게 아니므로 deque의 사이즈에서 남아있는 K만큼을 빼주고 출력.

 

성공