[BOJ] 백준 2493. 탑 (Gold V)

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

2493번: 탑

이 문제도 좀 유명한 편인데 뒤늦게 풀었다.

N은 50만, 시간 제한은 1.5초라 상한 시간복잡도는 O(NlgN)인 문제이다.

KOI 2009 지역본선 초등부 4번, 고등부 2번이기도 한 문제이다.

지역본선이라 그런지 난이도는 높지 않은 듯하다. (근데 애초에 초등학생이 이정도 문제 풀 정도면 대단한거 아닌가... 요즘 초등부 문제들이 워낙 괴랄해서 쉬워보이는건가...)

---

의식의 흐름 및 해설

처음엔 예제를 그림으로 그려보았다.

문제를 내가 많이 푼 편이어서 그런지는 모르겠는데, 이전 탑의 높이보다 큰지, 작은지에 따라 스택으로 왔다갔다 해서 O(N)에 풀 수 있는 전형적인 스택 문제처럼 보였다.

 

실제로 이 문제는 스택을 이용해서 푼다. 

나는 개인적으로 스택 문제는 거의 대부분 벡터로 해결하는 것 같다.

stack의 push, pop 기능도 벡터에 있고, 스택에 없는 기능 또한 벡터에 존재하기 때문이다.

 

일단 맨 처음 탑의 높이는 스택에 넣어준다.

그리고 다음 탑의 높이가 이전 탑의 높이보다 크면, 이전 탑에 닿을 일이 없으므로 이전 탑을 pop해준다.

만약 이전 탑이 여러 개라면, 이전 탑 중에서 다음 탑의 높이보다 큰 경우일 때까지 계속 pop을 해주고, 이 때 스택이 비어있는지 여부를 주의하도록 하자.

다음 탑의 높이가 이전 탑의 높이와 같은 경우는 없다. (문제에 적혀 있다.)

다음 탑의 높이가 이전 탑의 높이보다 낮다면, 그냥 push 해주면 된다.

 

전형적인 스택 문제이고 O(N)에 해결가능하다.

---

코드

#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> pi;
int N, n;
vector<pi> ans;
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> n;
	cout << 0 << " ";
	ans.push_back({ n, 1 });
	for (int i = 2; i <= N; i++) {
		int n;
		cin >> n;
		while (!ans.empty() && ans.back().first < n) {
			ans.pop_back();
		}
		cout << (ans.empty() ? 0 : ans.back().second) << " ";
		ans.push_back({ n, i });
	}
}