[BOJ] (Swift) 17298 - 오른수

17298번: 오큰수

문제 요약

• 크기가 N인 수열이 A가 있을 때 A[i]의 오른쪽에 있으면서 A[i] 보다 큰 수 중에 가장 왼쪽에 있는 수를 오큰수라 한다. 
• 수열 A의 모든 원소의 오큰수를 순서대로 출력하자. 단, 오큰수가 없는 경우에는 -1을 출력하자.

풀이

• 이중반복문으로 쉽게 할 수 있지만 당연하게도 시간 초과이다.
• 모든 원소가 -1 인 result 배열에 각 인덱스의 오큰수를 넣어주자.
• stack에는 오큰수를 찾지 못한 인덱스 번호를 넣어준다.
• 만약 스택의 가장 윗 원소(= 인덱스)에 해당하는 input[인덱스] 보다 큰 숫자가 나왔다면 해당 원소(= 인덱스)를 stack에서 pop 하면서 오큰수를 result[인덱스]에 넣어주자.

import Foundation

let N = Int(readLine()!)!
var input = readLine()!.split(separator: " ").map { Int($0)! }
var stack: [Int] = []
var result: [Int] = Array(repeating: -1, count: N)
for i in 0..<N {
    while !stack.isEmpty && input[stack.last!] < input[i] {
        result[stack.popLast()!] = input[i]
    }
    stack.append(i)
}

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

---

구현하는데 오래 걸렸다. 구글링도 많이함. 더 열심히 하자