[백준] 2812. 크게 만들기

오늘도 어김없이 시원하게 틀렸다.

이 문제의 특징은 각 자리의 숫자를 재배치 할 수 없다는 점이다.

애초에 재비치해서 가장 큰 숫자를 물어볼리가..

 

한참을 고민한끝에 다음 해법을 생각했다.

 

K개를 지워서 만들어지는 숫자는 N-K자리 숫자다.

서두에 말했듯 각 자리의 숫자는 재배치 할 수 없다.

따라서 가장 높은 자리의 숫자는 주어진 N자리 숫자의 특정 구간에서의 최댓값이다.

예시로 14315에서 2개의 숫자를 지운다고 해보자.

그럼 최종적으로 만들 숫자는 3자리 숫자이다.

따라서 백의자리 수에 들어갈 숫자는 앞 3개인 1, 4, 3 중 최댓값인 4이다.

왜 나머지 2개인 1, 5는 안되냐면, 둘중 하나라도 선택하면, 문제의 특징 때문에 3자리 수를 다 못채우기 때문이다.

십의 자리는 백의 자리로 선택한 4 이후부터 뒤에서 두번째인 1까지 이다.

이런 식으로 알고리즘을 짰고, 답은 잘 나왔으나..

 

시간초과가 떠버렸다.

 

왜냐하면 각 자리를 하나씩 집어넣어야해서 O(N)이 걸리고,

각 자리에 들어갈 숫자를 탐색할 때(최댓값을 찾을 때), O(N)이 걸리므로

최종적으로 O(N²)이기 때문이다. N은 최대 500,000 이므로 제한시간 1초를 훨씬 넘게된다.

 

※ 각 구간에서 최댓값을 찾는 방법은 구간트리가 있다. 그러면 최종적으로 O(NlogN)이 걸릴테니 시간초과는 안 날것이다. 하지만, N이 50만개나 되면 메모리제한에 걸리지는 않을지 걱정되서 안 해봤다. 해보면 이 글에 다시 적도록 하겠다.

 

멘붕이 와버렸다. 도저히 어떻게 해야할지 감이 안 잡혔기 때문이다.

아무리 고민해봐도 답이 안 나와서 해답을 찾아보니..

 

스택을 야무지게 사용했다..

 

주어진 수의 가장 높은 자리부터 하나씩 내려간다.

매번 스택에 넣는데, 규칙이 하나 있다.

만약 지금 보고있는 수보다 스택의 맨 위(top)에 있는 수가 작다면, 그 수는 삭제한다.

삭제시 K를 1씩 줄인다.

이는 스택이 아예 비워지거나, 스택의 맨 위에 있는 수가 같거나 더 클때까지 반복한다.

위 규칙은 K가 0보다 클때만 수행된다.

 

코드로 나타내면 다음과 같다.

for(int i=0; i<N; i++) {
	while(!tmp.empty() && K && s[i] > tmp.top()) {
		tmp.pop();
		K--;
	}
	tmp.push(s[i]);
}

 

[구간트리를 이용한 해법]

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;

int N, K;
string s;
vi arr, ret;
vector<pii > tree;

pii init(vi &arr, vector<pii > &tree, int node, int start, int end) {
	if(start == end) return tree[node] = make_pair(arr[start], start);
	pii left = init(arr, tree, node*2, start, (start+end)/2);
	pii right = init(arr, tree, node*2+1, (start+end)/2+1, end);
	if(left.first > right.first) return tree[node] = left;
	else {
		if(left.first < right.first) return tree[node] = right;
		else {
			if(left.second < right.second) return tree[node] = left;
			else return tree[node] = right;
		}
	} 
}

pii query(vi &arr, vector<pii > &tree, int node, int start, int end, int left, int right) {
	if(left > end || right < start) return make_pair(-1, -1);
	if(left <= start && end <= right) return tree[node];
	pii leftNode = query(arr, tree, node*2, start, (start+end)/2, left, right);
	pii rightNode = query(arr, tree, node*2+1, (start+end)/2+1, end, left, right);
	if(leftNode.first > rightNode.first) return leftNode;
	else {
		if(leftNode.first < rightNode.first) return rightNode;
		else {
			if(leftNode.second < rightNode.second) return leftNode;
			else return rightNode;
		}
	} 
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N >> K;
	cin >> s;
	
	arr.resize(N);
	tree.resize(N*4);
	
	for(int i=0; i<N; i++) arr[i] = s[i] - '0';
	
	init(arr, tree, 1, 0, N-1);
	
	int start, end;
	start = -1;
	end = K;
	while(N-K) {
		pii q = query(arr, tree, 1, 0, N-1, start+1, end);
		ret.push_back(q.first);
		start = q.second;
		end++;
		K++;
	}
	
	int size = ret.size();
	for(int i=0; i<size; i++) cout << ret[i];
	cout << "\n";
}

구간트리로 해보니 가능했다!!

그리디 알고리즘과 비교하여, 약 10배가 차이나는 풀이지만 그래도 생각한 그대로 풀리니 기분이 좋다.

 

[왜 그랬을까?]

이번 풀이는 정말 상상도 못했다. 생각보다 간단하긴 한데.. 그렇다고 계속 고민해서 떠오를 아이디어가 아니었다ㅠㅠ