[그리디 #19] BOJ 2812 - 크게 만들기

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

2812번: 크게 만들기

 

접근 방법

심플하면서 어려운 문제이다.

n자리 수에서 m개의 수를 제거하여 가장 큰 수를 만드는 문제이다.

 

예제 3번에 이 문제에 힌트가 있다.

 

4 1 7 7 2 5 2 8 4 1

에서 4개를 제거하여

775841

를 만들어야 한다.

 

핵심은 4와 1을 제거하여 7을 가장 높은 자릿수로 만들어야 한다는 것!

 

예전에 스택을 이용하여 괄호가 포함된 중위 표기법을 후위 표기법으로 고치던게 생각이 났다.

스택에 숫자들을 넣고, 현재 숫자보다 작은 숫자들은 제거하는 방식으로 진행하여 좋겠다고 생각했다.

 

따라서, 알고리즘은 다음과 같다.

 

cnt: 숫자 제거한 횟수

 

1. 숫자를 돌면서 자기 자신 보다 스택의 pop이 작은 경우, pop을 해서 제거한다. 단, cnt가 m보다 작을 경우 수행

( while(cnt < m && curr > s.pop()) )

2. 그러고 나서 스택에 자기 자신을 넣는다. ( s.push(curr) )

3. 스택을 그대로 pop하게 되면 남아있는 숫자들이 역순으로 나온다. 이를 정순으로 출력하면 끝!

 

 

주의 사항

75%에서 오류가 나서 생각을 해보니 다음 경우에 반례가 존재한다.

5 1
5 4 3 2 1

 

 

위 경우에는 내림차순으로 들어오기 때문에 위 알고리즘을 피해간다.

따라서, cnt가 m보다 작을 동안 뒷자리를 pop하면 된다.

( while(cnt < m) { s.pop(); cnt++; } )

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <string>
#include <cmath>

#define MAX 1010
#define INF 987654321

using namespace std;

int n, m;
string str;
vector<int> v;
stack<int> s;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	cin >> str;
	for (int i = 0; i < str.length(); i++) {

		v.push_back((int)(str[i]-'0'));
		//cout << v[i] << endl;
	}

	int cnt = 0;
	s.push(v[0]);
	for (int i = 1; i < v.size(); i++) {
		while (!s.empty() && (cnt < m && s.top() < v[i])) {
			//cout << "poped: " << s.top() << endl;
			s.pop();
			cnt++;
		}
		s.push(v[i]);
	}
	// cnt m으로 맞추기
	while (cnt < m) {
		s.pop();
		cnt++;
	}

	// 출력
	v.clear();
	while (!s.empty()) {
		v.push_back(s.top());
		s.pop();
	}

	for (int i = v.size()-1; i >= 0; i--) {
		cout << v[i];
	}
}

이번에는 운이 좋았던거 같다...

열심히 공부해나가자