BOJ 2493:: 탑 – 스택
http://acmicpc.net/problem/2493
스택을 쓰는 아주 유명한 문제입니다. (Stock span problem이라고 합니다.)
무식하게 풀면 $O(n^2)$이니까 시간초과 납니다. 하지만 스택을 사용하면 $O(n)$으로 줄일 수 있습니다.
- 탑의 높이를 받습니다. ($h$라고 합시다)
- 스택이 비거나 스택의 top이 $h$ 이상일 때까지 계속 pop합니다.
- 스택이 비어서 더 pop이 불가능하다면 레이저를 받는 탑이 없는 겁니다.
- 스택의 top이 $h$ 이상이라면 top이 바로 레이저를 받는 탑의 높이입니다.
- $h$를 스택에 push합니다.
실제로는 이 탑이 쏜 레이저를 받는 탑의 높이를 요구한 게 아니라 몇 번째인지 알아내라고 했으니까 스택에 탑의 높이 말고도 인덱스도 저장해야 합니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include<cstdio> #include<stack> #include<utility> using namespace std; int main(void) { int n, h; stack<pair<int, int>> S; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &h); while (!S.empty() && S.top().first < h) S.pop(); if (S.empty()) printf("0 "); else printf("%d ", S.top().second); S.push(make_pair(h, i)); } return 0; } |