백준 2812(크게 만들기) c++

문제

2812번: 크게 만들기

숫자를 입력받아 k 개의 숫자를 빼서 가장 큰 수를 출력하는 문제입니다.

문제는 간단하지만 구현하는게 생각이 많았습니다.

---

int n, k;
cin >> n >> k;

string st;
cin >> st;

먼저 숫자의 갯수 n 과 몇개를 빼는지 k를 입력받습니다.

숫자는 string으로 입력받는데 n의 범위가 500000까지 이기 때문입니다.

---

vector<int>v;
deque<int>q;
q.push_back(st[0] - '0');

벡터 v는 완성된 숫자를 넣어줄 공간입니다.

덱 q는 string으로 부터 숫자를 받아 저장할 임시 공간입니다.

먼저 q에 첫번째 자리 숫자를 넣어줍니다. 

그래야 다음 들어올 숫자로부터 비교해줄 수 있기 때문입니다.

---

for (int i = 1; i < n; i++) {
		if (i <= k) {
			while (!q.empty()&&q.back() < st[i] - '0')
				q.pop_back();
			q.push_back(st[i] - '0');
		}
		else {
			v.push_back(q.front());
			q.pop_front();
			while (!q.empty() && q.back() < st[i] - '0')
				q.pop_back();
			q.push_back(st[i] - '0');
		}
	}

i가 1부터 시작하는데 방금전에 첫번째 숫자자리를 q에 넣어주었기 때문입니다.

if 절을 보면 조건이 ' i<=k ' 입니다.

이것은 첫번째 자릿수가 바뀔 가능성이 있는 경우 입니다.

따라서 while절로 부터 새로들어올 원소가 첫번째 자릿수보다 큰경우 계속해서 pop을 해주어서

첫번째 자리까지 들어갈 수 있습니다.

반면에 else절에서는 더이상 들어올 원소는 첫번째 자릿수에 들어가지 못하는 경우입니다.

그래서 q의 맨앞의 숫자를 v로 옮기고 pop해줍니다. 

다시 또 while절을 통해 새로들어온 원소를 넣어줍니다.

---

v.push_back(q.front());
for (int i = 0; i < n - k ; i++) {
	cout << v[i];
}

 for문이 끝나면 q.front()에 마지막 원소가 들어있으므로 이것을 v에 옮겨 주면 숫자가 완성됩니다.

마지막으로 v를 출력해주면 됩니다.

---

아마 코드가 복잡한데 아직 효율적으로 코드를 짜는게 어렵습니다.

더 연습해야할것 같습니다.

---

전체코드 입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n, k;
	cin >> n >> k;

	string st;
	cin >> st;
	
	vector<int>v;
	deque<int>q;
	q.push_back(st[0] - '0');
	for (int i = 1; i < n; i++) {
		if (i <= k) {
			while (!q.empty()&&q.back() < st[i] - '0')
				q.pop_back();
			q.push_back(st[i] - '0');
		}
		else {
			v.push_back(q.front());
			q.pop_front();
			while (!q.empty() && q.back() < st[i] - '0')
				q.pop_back();
			q.push_back(st[i] - '0');
		}
	}
	v.push_back(q.front());
	for (int i = 0; i < n - k ; i++) {
		cout << v[i];
	}


	
	return 0;
}