Algorithm / 택배상자

문제

프로그래머스 / 택배상자

1) 문제 풀이

func solution(_ order:[Int]) -> Int {
    var heap: [Int] = []
    var answer: [Int] = []
    var index = 0
    var next = order[order[answer.count] - 1]
    
    while index < order.count {
        let current = order[index]
        
        if current == next {
            answer.append(current)
            let nextIndex = answer.count < order.count ? order[answer.count] - 1 : 0
            next = order[nextIndex]
        }
        
        while heap.last == next {
            answer.append(heap.removeLast())
            let nextIndex = answer.count < order.count ? order[answer.count] - 1 : 0
            next = order[nextIndex]
        }
        
        if !answer.contains(current) {
            heap.append(current)
        }
        
        index += 1
    }
    
    return answer.count
}

결과

2) 코드 개선

🚨 문제점

• answer.contains(current)의 사용 → O(n)
  • 매번 answer.contains(current)로 현재 상자가 이미 배송되었는지 확인 중
  • 이 연산은 O(n)이어서 최악의 경우 O(n²)로 시간 초과 위험이 있음
• answer 배열에 불필요한 중복 저장
  • 배송된 상자를 answer에 계속 append하고, 이후에 answer.count로 인덱스를 계산
  • 사실 배송된 개수만 알면 되므로 배열 대시 Int 카운터만 쓰는 것이 더 효율적
• next 계산 방식이 복잡
  • 매번 answer.count를 기준으로 order[answer.count] - 1 같은 인덱스를 계산 중
  • 이는 이해하기 어렵고 인덱스 범위 에러 가능성도 있음
• 로직의 핵심 흐름이 불필요하게 꼬여 있음
  • 본래 스택 문제는 단순히
    • 메인 벨트에서 상자를 하나씩 꺼내면서
    • 원하는 순서와 같으면 바로 배송
    • 다르면 보조 스택에 쌓음
    • 스택 top이 원하는 순서와 같을 때까지 pop
  • 이렇게 단순히 처리할 수 있는데, 코드가 불필요하게 복잡해짐

✅ 개선 방법

• 각 상자는 한 번 push + 한 번 pop
  • 시간 복잡도는 O(n)
  • order.count가 최대 100,000이어도 충분히 빠름

func solution(_ order: [Int]) -> Int {
    var stack: [Int] = []   // 보조 컨테이너 벨트 (스택)
    var current = 1         // 메인 벨트에서 꺼낼 번호
    var delivered = 0       // 배송된 상자 개수
    
    for target in order {
        // target까지 메인 벨트에서 상자를 꺼냄
        while current <= target {
            stack.append(current)
            current += 1
        }
        
        // 스택의 마지막이 원하는 상자라면 배송
        if stack.last == target {
            stack.removeLast()
            delivered += 1
        } else {
            // 스택 top이 다르면 배송 불가 → 중단
            break
        }
    }
    
    return delivered
}

결과