BOJ 2493:: 탑 – 스택

Posted on by

http://acmicpc.net/problem/2493

스택을 쓰는 아주 유명한 문제입니다. (Stock span problem이라고 합니다.)

 

무식하게 풀면 $O(n^2)$이니까 시간초과 납니다. 하지만 스택을 사용하면 $O(n)$으로 줄일 수 있습니다.

  1. 탑의 높이를 받습니다. ($h$라고 합시다)
  2. 스택이 비거나 스택의 top이 $h$ 이상일 때까지 계속 pop합니다.
    1. 스택이 비어서 더 pop이 불가능하다면 레이저를 받는 탑이 없는 겁니다.
    2. 스택의 top이 $h$ 이상이라면 top이 바로 레이저를 받는 탑의 높이입니다.
  3. $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;
}