BOJ - 2493. 탑 (C++)

2493. 스택의 시간복잡도 (Monotonic Stack)

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

2493번: 탑

 

[풀이]

벡터로도 풀 수 있고 스택으로도 풀 수 있는 문제이다. 하지만 첫 번째 코드인 벡터을 사용한 코드는 시간초과가 발생하고 두 번째 코드인 스택을 사용한 코드는 solved 를 받는다. 두 코드 모두 for문 안에 while 문이 들어간 시간 복잡도 O(N) 코드처럼 보이는데 왜 실행 시간이 다를까 (물론 vector가 아닌 배열로 작성해도 시간초과가 발생한다)

 

1) vector 사용

#include <bits/stdc++.h>
using namespace std;
vector <int> height;
int N;

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	height.push_back(1e9+1);
	cin >> N;
	for (int i=1; i<=N; i++) {
		for (int it:height) cout << it << ' ';
		cout << endl;

		int tmp;
		cin >> tmp;
		int k=i-1;
		while(1){
			if (height[k] >= tmp) {
				cout << k << ' '; 
				break;
			}
			k--;
		}
		height.push_back(tmp);
	}
}

2) stack 사용

#include <bits/stdc++.h>
using namespace std;
stack <pair<int, int>> height;
int N;

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	height.push({0, 1e9+1});
	cin >> N;
	for (int i=1; i<=N; i++) {
		int tmp;
		cin >> tmp;
		while(1){
			if (height.top().second >= tmp){
				cout << height.top().first << ' ';
				break;
			}
			height.pop();
		}
		height.push({i, tmp});
	}	
}

 

두 코드를 나란히 두고 비교해보자.

만약 입력하는 탑의 높이가  9 6 5 7 4 라면

벡터의 경우는 충분히 단계가 진행되고 height가 {1e9+1, 9, 6, 5} 이며 tmp로 7이 들어올 때 height의 뒤에서부터 5, 6, 9 순서로 비교하다 9에서 break를 하게 된다. 즉 비교를 할 때 자신보다 앞에 있는 모든 탑의 높이와 비교하게 된다.

반면에 스택은 같은 단계에서 각 단계에 pop하는 과정이 있어 height가 <1e9+1, 9, 5>인 상태에서 tmp로 7이 들어오면 5와 비교한 뒤 pop하고 9와 비교해서 break를 하게 된다. 즉 스택은 불필요한 비교 과정을 pop을 통해 제거한다.

 

Monotonic Stack을 통해 한쪽 방향으로 여러 정수들 중 자신보다 큰 가장 가까운 값을 찾는데 시간복잡도를 O(N)으로 해결할 수 있다.