[프로그래머스] 택배상자

문제

프로그래머스

입력

order:[Int] = 택배 트럭에 실어야하는 순서

결과

ans: Int = 원하는 순서로 실을 수 있는 최대 상자

해석

현재 컨베이어 벨트에 있는 순서는 항상 [1...n] 순으로 있고 앞에서부터 뺄 수 있다.

이후 택배 트럭에 실어야할 순서인 상자가 아니면 stack에 임시로 넣고 아니면 바로 뺀다.

 

정리하면 택배 상자를 내릴 수 있는 경우의 수는 2가지다.

• 컨베이어 벨트에서 뺀다.
• 스택에서 뺀다. 단, 스택은 가장 최근에 실은 순으로 뺄 수 있다.

코드

import Foundation

func solution(_ order:[Int]) -> Int {
    let n = order.count
    var priority: [Int] = [Int](repeating: 0, count: n) // 우선순위
    
    for i in 0..<n {
        priority[order[i]-1] = i
    }
    
    var target: Int = 0 // 현재 꺼내야하는 우선순위
    var stack: [Int] = []
    
    for i in 0..<n {
        if target == priority[i] { // 현재 target과 i의 우선순위가 같다면
            target += 1 
        } else {
            stack.append(priority[i]) // 아니면 스택
        }
        
         while !stack.isEmpty && stack.last! == target {
                let _ = stack.popLast()
                target += 1
        }
        
    }
    
    return target 
}