BOJ 2493:: 탑 – 스택

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합니다.

실제로는 이 탑이 쏜 레이저를 받는 탑의 높이를 요구한 게 아니라 몇 번째인지 알아내라고 했으니까 스택에 탑의 높이 말고도 인덱스도 저장해야 합니다.