[백준] 2812번 크게 만들기

문제

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

입력

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

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

출력

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

 

너무 안풀려서 다른 글을 참조해서 작성하였다.

처음 접근을 했을 때, 가장 작은거 k개만 빼면 되는 줄 알았다.

하지만 어디에도 정렬하라는 소리도, 암시도 없었다.

그냥 k개를 지웠을때 얻을 수 있는 값을 물어 보았다. 이는 1234에서 2개를 뺏을때 얻을 수 있는 값은

34, 24 , 23, 12, 13, 14,.. 등등 

즉, 숫자들의 순서는 바꾸면 안된다. 물론 이 말또한 어디에도 작성되어있지는 않지만...

그냥 단순히 지우라고만 했기 때문에 이런 추측이 가능한것 같다.

처음에는 몰랐지만...ㅜㅜ

 

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


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

  int n,k;
  cin >> n >> k;
  string str;
  cin >> str;

  deque<char> dq;
  for(int i = 0; i<str.length();i++) {
   while(k > 0&& !dq.empty()&& dq.back() < str[i]) {
     dq.pop_back();
     k--;
   }

   dq.push_back(str[i]);
  }

  for(int i = 0; i< dq.size()-k;i++) {
    cout << dq[i];
  }


  
}

 코드를 보면 생각보다 간단하다는 것과

생각보다 이해되지 않는게 있는다는 것을 알 수 있다..

간단한거야 코드가 짧으니.. 그런거고...

이해가 되지 않는건 왜 덱을 썼는지... k는 왜 뻇는지... 그런게 너무 이상하다고 느꼈다.

 

사실 덱이 아니라 스택을 써도 된다.

이들을 사용하는 이유는 숫자의 순서를 바꾸지 하지 않기 위해 이다.

 

가장 위에 있는 숫자는 지금  인덱스의 숫자와 비교가 들어가고... 그게 작은지 큰지비교합니다.

그럼 자연스럽게 숫자가 쌓이겠죠?

 

1 2 3 4 가 들어가면 나오는 숫자도 1 2 3 4 가 나옵니다. 왜냐하면 덱 혹은 스택이니까여...

이 성질을 이용하면 쉽게? 풀 수 있을 겁니다.(난 아니지만.ㅜㅜ)

 

근데 갑자기 K를 while문안에 뺴는 이유가 궁금할지도 모릅니다.

이건 숫자를 제거하고 k를 감소를 시키기 위한 하나의 방법이라고 생각하면 될것 같습니다.

 

using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

queue<int> que[10];
int n, k;
char buf[500005];
string ret;

int main(){
	scanf("%d %d %s",&n,&k,buf);
	for(int i=0; i<n; i++){
		que[buf[i] - '0'].push(i);
	}
	int t = 0;
	k = n-k;
	for(int j=0; j<k; j++){
		for(int i=9; i>=0; i--){
			while(!que[i].empty() && que[i].front() < t) que[i].pop();
			if(que[i].size() && ret.size() + n - que[i].front() >= k){
				t = que[i].front();
				ret.push_back(i + '0');
				que[i].pop();
				break;
			}
		}
	}
	puts(ret.c_str());
}