백준 2493번 - 탑 (C++)

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

2493번: 탑

 

단순히 답만 구하려면 쉬운 문제이다. 그러나 그렇게 풀면 시간복잡도가 O(N^2) 이 되어버린다.

 

처음에는 큐를 사용하여 

 

6 9 5 7 4 라면 맨 뒤부터 시작해서 큐에 4를 넣고 뒤에서부터 비교하며

 

7을 만났을 때 => 큐의 모든 값과 비교 4 제거, 7을 큐에 삽입 현재 큐 : ( 7 )

5를 만났을 때 => 큐의 모든 값과 비교 7 을 놔두고 5를 삽입 현재 큐 : ( 7 , 5 )

9를 만났을 때 => 큐의 모든 값과 비교 5, 7 모두 제거, 9를 삽입 현재 큐 : ( 9 )

6을 만났을 때 => 큐의 모든 값과 비교 모두 불가하므로 6을 삽입 현재큐 : (9, 6)

 

수신이 가능하면 그 자릿수를 저장하는 식으로 구현했다. 이러면 O(N) 까지는 안되겠지만 적어도 O(N^2)는 아닐 것이라 생각하여 제출했는데 시간초과를 받았다.

 

그런데 잘 생각해보니 최소값만 비교하면 되었다. 다시말해 예를들어

큐에 10, 9, 8 순으로 들어있고 지금 만난 기둥의 길이가 2라고 해보자.

 

위의 방식으로하면 10, 9, 8을 모두 비교해야한다. 하지만 최소 우선순위큐라면? 

 

8을 먼저 비교하고 최소인 8도 수신할 수 없는데 이보다 큰 것들을 수신할 수 있을리가 없다. -> 불필요한 비교를 줄일 수 있다.

 

그러나 문제를 풀고보니 문제의 분류가 스택이었다. 그리고 내 코드보다 다른 사람들의 코드가 훨씬 빨랐다. 이 문제의 정 해는 스택을 활용한 풀이었다.

 

이를 Monotonic stack 이라한다는데 한 번 공부해봐야겠다.

 

스택을 이용한 풀이의 로직은 다음과 같다.

1. 스택이 비어있다면 0

2. 스택에 지금 높이 저장

3. 다음으로 넘어가서 이전의 기둥들을 모두 비교하며 pop -> 모두 팝해도 되는 왼쪽에서 오른쪽으로 가고 있기 때문이다. 지금 기둥보다 작다면 이후 오른쪽의 기둥들의 수신을 받을 수 있을 리가 없다.

4. 수신가능하면 pop하지 않고 break -> 이후 오른쪽의 기둥들의 정보를 수신할 수 있다.

 

문제는 풀었지만, 정해가 아니었다. 

 

두 코드는 모두 접근 시간복잡도 O(1)을 제외하고 꼭 N번의 pop이 일어난다. 

그리고 stack의 pop은 O(1)이고, 우선순위큐의 시간복잡도는 O(logN)이다.

 

그러므로 내 풀이는 O(NlogN), 정 해는 O(N)의 시간복잡도를 가진다.

 

우선순위큐 활용 코드

#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;

map<int, int> answer_map;
int tower[500001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N;

	priority_queue<int> wait_q;

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> tower[i]; // 6 9 5 7 4
	}

	wait_q.push(-tower[N - 1]);

	for (int i = N - 2; i > -1; i--) {
		int now_top = tower[i];
		
		int iter = wait_q.size();
		for (int j = 0; j < iter; j++) {
			int tmp = -wait_q.top();
			wait_q.pop();
			if (tmp <= now_top) { // 수신가능
				answer_map.insert({ tmp, i + 1 });
			}
			else {
				wait_q.push(-tmp);
				break;
			}
		}
		wait_q.push(-now_top);
	}

	while (!wait_q.empty()) {
		answer_map.insert({ wait_q.top(), 0 });
		wait_q.pop();
	}

	for (int i = 0; i < N; i++) {
		cout << answer_map[tower[i]] << " ";
	}
}

 

 

#include <iostream>
#include <stack>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	stack<pair<int, int>> stk;

	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;

		while (!stk.empty()) {
			int now = stk.top().second;
			int idx = stk.top().first;
			if (now >= tmp) { // 수신 가능
				cout << idx << " ";
				break;
			}
			else {
				stk.pop();
			}
		}
		
		if(stk.empty()){
			cout << 0 << " ";
		}

		stk.push({ i + 1, tmp });
	}
}