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합니다.
실제로는 이 탑이 쏜 레이저를 받는 탑의 높이를 요구한 게 아니라 몇 번째인지 알아내라고 했으니까 스택에 탑의 높이 말고도 인덱스도 저장해야 합니다.
#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; }
좋은 풀이 감사합니다~^^
그런데, 스택 S를 정의하는 곳에서 > 두 개가 붙으면 비트연산? 쉬프트? 같은 것으로 인식해서 >> 대신 > >을 사용해야 할 것 같습니다. 즉, stack<pair > S;가 맞는 것 같습니다.
죄송합니다. stack S;가 아니라 stack<pair > S;이네요^^
아, 블로그 댓글 기능이 약간 이상한 것이였네요
Modern C++에서는 필요 없습니다.