백준 - 탑 (2493)

let N = Int(readLine()!)!
let height = readLine()!.split(separator: " ").map { Int(String($0))! }
var stack = [0]
var answer = "0 "

for i in 1..<N {
    while !stack.isEmpty && height[stack.last!] < height[i] {
        stack.removeLast()
    }
    answer += "\(stack.isEmpty ? 0 : stack.last! + 1) "
    stack.append(i)
}

print(answer)

• 왼쪽부터 각 탑들의 높이를 확인한다.
  • 지금까지 봤던 탑 중 가장 오른쪽에 있는 탑보다 높이가 낮다면 다음에 이 탑이 신호를 수신 받을 가능성이 있다.
  • 지금까지 봤던 탑들보다 높이가 더 크다면, 이전에 있던 낮은 탑들은 더 이상 신호를 수신받을 수 없다.
    • 따라서 이 탑보다 높이가 작은 탑들은 스택에서 모두 pop해준다.
• 위 과정을 거친 후 스택의 top에 저장된 탑이 신호를 수신받는 탑이 된다. 만약 스택이 비어있다면 신호를 수신받는 탑이 없는 것이다.
  • 이 값을 정답 변수에 저장한 후 현재 보고 있는 탑을 스택에 push한다.