2493번: 탑

문제 풀이

무대포 완전 탐색 (🚫 시간 초과)

처음으로 그냥 아무 생각없이 아래와 같이 구현할 수 도 있습니다. 정직하게(?) 각각의 탑 마다 레이저가 닿는 탑을 완전탐색으로 구하는 방법이죠. 하지만 이 문제의 N은 최대 500,000입니다. 반면에 아래 알고리즘은 O(N^2)이죠. 무조건 시간초과가 납니다.

// 무대포 완전탐색
let N = Int(readLine()!)!
let towers = readLine()!.split(separator: " ").map { Int(String($0))! }
var results = [Int]()

outerLoop: for i in (0..<N).reversed() {
    var now = i - 1
    innerLoop: while now >= 0 {
        if towers[now] > towers[i] {
            results.append(now + 1)
            continue outerLoop
        }
        now -= 1
    }
    results.append(0)
}

print(results.reversed().map{ String($0) }.joined(separator: " "))

O(N)의 방법을 찾아라! : Stack 활용하기

오른쪽 탑이 왼쪽 탑보다 작다면 왼쪽 탑은 오른쪽 탑에서 송신하는 레이저를 수신할 수 있습니다. 만약에 오른쪽 탑이 왼쪽 탑 보다 크다면 왼쪽 탑은 송신할 수 없죠.

따라서 오른쪽 탑 부터 시작해서 아직 송신할 탑을 찾지 못한 탑들을 stack에 넣어두고 왼쪽 탑이 stack에 있는 탑들 (오른쪽에 있는 탑들)보다 크다면 stack에서 pop한 탑들의 송신탑을 왼쪽 탑으로 저장하면 됩니다.

오큰수의 원리와 동일합니다.

// stack을 활용한 풀이
let N = Int(readLine()!)!
let towers = readLine()!.split(separator: " ").map { Int(String($0))! }
var results = Array(repeating: 0, count: N)
var stack = [Int]()

for i in (0..<N).reversed() {
    while !stack.isEmpty && towers[i] > towers[stack.last!] {
        let popped = stack.popLast()!
        results[popped] = i + 1
    }
    stack.append(i)
}

print(results.map{ String($0) }.joined(separator: " "))