백준 2493번: 탑 - Swift

https://www.acmicpc.net/problem/2493

난이도 - 골드 5 🥇

알고리즘 분류: 스택

🧐 문제접근

가장 쉬운 방법으로 생각하면
i번째 탑을 검사하려면, i-1, i-2, i-3 .. 을 탐색하면서
i번째 탑보다 큰 탑을 만날때가 답이다.

근데 당연히 이런식으로 하면, 시간복잡도가 O(N^2)이 되서 시간초과가 발생한다.

앞에서 부터 탐색을 하지 않고, 뒤에서 부터 탐색을 수행하면 O(N) 시간에 수행이 가능하다.

먼저 아직 더 높은 탑을 만나지 못한 탑들은 stack 에 들어가있다
<- 방향으로 탐색을 진행하면서, 이번에 마주친 탑과 stack에 들어가 있는 탑을 비교한다.
더 높은 탑을 마주쳤다면, stack에 있는 탑을 pop해주면서 ans을 갱신해주면 된다!

전체코드

//2493번 탑
let n = Int(readLine()!)!
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}

var stack = [Int]()
var ans = Array(repeating: 0, count: n)

for i in stride(from: n-1, to: -1, by: -1) {
    while !stack.isEmpty && arr[i] > arr[stack.last!] {
        let idx = stack.removeLast()
        ans[idx] = i + 1
    }
    stack.append(i)
}

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

한줄평가: 정형화된 유형인것 같다..!