[백준 - Swift] 1874 스택 수열

문제

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

1874번: 스택 수열

 

 

풀이

 1. 1에서 n까지 반복문을 돌면서 - O(10^5)

 2. 각 시행에서 stack에 push하고 result에 "+" 추가 - O(1)

 3. 각 시행에서 while문으로 pop해야할 게 없을 때까지 처리 (총 순회가 O(10^5)라서 괜츈)

 4. 2&3 반복문으로 돌림

 5. targets의 isEmpty에 따라 정답 출력

 

전체적으로 Array의 O(1) 연산을 이용하기 위해 기존 배열을 역순으로 바꾸었다. while문 내부에서 last를 적극적으로 사용하여 연산을 가볍게 가져가려 했다.

 

 

코드

let N = Int(readLine()!)!
var targets = Array(repeating: 0, count: N)
var stack = [Int](), arr = [Int](), result = [String]()

Array(0..<N).reversed().forEach{ targets[$0] = Int(readLine()!)! }

for i in 1...N {
    stack.append(i)
    result.append("+")
    
    while let last = stack.last, let target = targets.last, last == target {
        arr.append(stack.removeLast())
        result.append("-")
        targets.removeLast()
    }
}

if targets.isEmpty {
    result.forEach{ print($0) }
} else {
    print("NO")
}