PS/프로그래머스

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

Hamp 2024. 10. 2. 23:27
반응형

문제

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

입력

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 
}

 

반응형