[Java & Python] 프로그래머스: 택배상자

https://school.programmers.co.kr/learn/courses/30/lessons/131704?language=python3 

프로그래머스

문제 풀이

택배는 1부터 n까지 순서대로 들어옵니다.

택배 순서와 스케줄이 맞으면 바로 처리하고, 그렇지 않으면 무조건 서브컨베이어에 넣습니다.

그 후 서브컨베이어와 스케줄을 비교하여 맞으면 계속 처리합니다.

n번째 택배까지 처리한 다음 처리된 만큼의 택배 숫자를 반환합니다.

 

Stack과 Queue 자료형을 잘 활용하는 것이 중요한 문제였습니다.

단, Python의 경우 list로 처리할 경우 시간초과되므로 deque 자료형을 이용해서 풀이해야 합니다.

Java

import java.util.*;

class Solution {
    public int solution(int[] order) {

        Stack<Integer> subConveyor = new Stack<>(); // 서브컨베이어
        Queue<Integer> schedule = new LinkedList<>(); // 스케줄

        // 스케줄에 주어진 대로 삽입
        for (int singleOrder : order){
            schedule.add(singleOrder);
        }

        int loads = order.length; // 전체 택배 숫자
        int currentPackage = 1; // 현재 택배 번호

        while (!schedule.isEmpty() && currentPackage <= loads) {

            // 스케줄과 택배 순서가 맞으면
            if (schedule.peek() == currentPackage) {
                schedule.poll();
            }
            // 안 맞으면 서브컨베이어에 넣기
            else {
                subConveyor.push(currentPackage);
            }

            // 서브컨베이어와 스케줄이 일치하는 동안 계속 내리기
            while (!subConveyor.empty() && !schedule.isEmpty() && Objects.equals(schedule.peek(), subConveyor.peek())) {
                schedule.poll();
                subConveyor.pop();
            }

            // 현재 택배 번호 증가
            currentPackage++;
        }

        // 전체 숫자에서 줄어든 만큼 반환
        return loads - schedule.size();
    }
}

Python

from collections import deque


def solution(order):
    sub_conveyor: deque = deque()  # 서브컨베이어
    schedule: deque = deque(order)  # 스케줄
    entire_load: int = len(order)  # 전체 택배 숫자
    current_package: int = 1  # 현재 택배 번호

    while schedule and current_package <= entire_load:
        # 스케줄과 택배 번호가 맞으면
        if schedule[0] == current_package:
            schedule.popleft()
        # 그렇지 않으면 서브컨베이어로
        else:
            sub_conveyor.append(current_package)

        # 스케줄과 서브컨베이어가 일치하는 동안에는 계속 내리기
        while sub_conveyor and schedule and sub_conveyor[-1] == schedule[0]:
            sub_conveyor.pop()
            schedule.popleft()
        # 현재 택배 번호 증가
        current_package += 1

    # 스케줄에서 줄어든 만큼 반환
    return entire_load - len(schedule)