알고리즘 코드카타 106 - 택배상자

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

프로그래머스

문제 설명
영재는 택배상자를 트럭에 싣는 일을 합니다. 영재가 실어야 하는 택배상자는 크기가 모두 같으며 1번 상자부터 n번 상자까지 번호가 증가하는 순서대로 컨테이너 벨트에 일렬로 놓여 영재에게 전달됩니다. 컨테이너 벨트는 한 방향으로만 진행이 가능해서 벨트에 놓인 순서대로(1번 상자부터) 상자를 내릴 수 있습니다. 하지만 컨테이너 벨트에 놓인 순서대로 택배상자를 내려 바로 트럭에 싣게 되면 택배 기사님이 배달하는 순서와 택배상자가 실려 있는 순서가 맞지 않아 배달에 차질이 생깁니다. 따라서 택배 기사님이 미리 알려준 순서에 맞게 영재가 택배상자를 실어야 합니다.

만약 컨테이너 벨트의 맨 앞에 놓인 상자가 현재 트럭에 실어야 하는 순서가 아니라면 그 상자를 트럭에 실을 순서가 될 때까지 잠시 다른 곳에 보관해야 합니다. 하지만 고객의 물건을 함부로 땅에 둘 수 없어 보조 컨테이너 벨트를 추가로 설치하였습니다. 보조 컨테이너 벨트는 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있습니다(즉, 가장 마지막에 보조 컨테이너 벨트에 보관한 상자부터 꺼내게 됩니다). 보조 컨테이너 벨트를 이용해도 기사님이 원하는 순서대로 상자를 싣지 못 한다면, 더 이상 상자를 싣지 않습니다.

예를 들어, 영재가 5개의 상자를 실어야 하며, 택배 기사님이 알려준 순서가 기존의 컨테이너 벨트에 네 번째, 세 번째, 첫 번째, 두 번째, 다섯 번째 놓인 택배상자 순서인 경우, 영재는 우선 첫 번째, 두 번째, 세 번째 상자를 보조 컨테이너 벨트에 보관합니다. 그 후 네 번째 상자를 트럭에 싣고 보조 컨테이너 벨트에서 세 번째 상자 빼서 트럭에싣습니다. 다음으로 첫 번째 상자를 실어야 하지만 보조 컨테이너 벨트에서는 두 번째 상자를, 기존의 컨테이너 벨트에는 다섯 번째 상자를 꺼낼 수 있기 때문에 더이상의 상자는 실을 수 없습니다. 따라서 트럭에는 2개의 상자만 실리게 됩니다.

택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order가 주어졌을 때, 영재가 몇 개의 상자를 실을 수 있는지 return 하는 solution 함수를 완성하세요.

제한사항
1 ≤ order의 길이 ≤ 1,000,000
order는 1이상 order의 길이 이하의 모든 정수가 한번씩 등장합니다.
order[i]는 기존의 컨테이너 벨트에 order[i]번째 상자를 i+1번째로 트럭에 실어야 함을 의미합니다.

 

 

지정한 순번대로 트럭에 택배를 싣는 알고리즘, 더이상 실을 수 없을 때 종료한다.

def solution(order):
    answer = 0
    main_container = list(range(1, len(order)+1))
    sub_container = []

 

실어야하는 택배가 순서대로 담겨있는 main_container와 순번을 조정할 수 있는 sub_container를 생성한다.

 

while not sub_container:
        if main_container[0] == order[0]:
            main_container.pop(0)
            order.pop(0)
            answer += 1
        else:
            sub_container.insert(0, main_container[0])
            main_container.pop(0)

 

main_container의 가장 앞에 높인 택배가 기사님이 요청한 순번과 같을 경우 그 택배를 트럭에 싣는다. 그리고 요청을 제거한 후 트럭에 실린 택배의 수(answer)를 증가시킨다.

요청한 순번과 다를 경우 택배를 보조컨테이너의 맨앞에 싣는다. 그리고 해당 구문을 sub_container에 원소가 추가될 때까지 반복한다.

 

while sub_container:
            if main_container and main_container[0] == order[0]:
                main_container.pop(0)
                order.pop(0)
                answer += 1
            elif sub_container[0] == order[0]:
                sub_container.pop(0)
                order.pop(0)
                answer += 1
            else:
                sub_container.insert(0, main_container[0])
                main_container.pop(0)
            if order and order[0] in sub_container and order[0] != sub_container[0]:
                return answer

 

sub_container에 원소가 있을 경우 sub_container의 가장 앞, 또는 main_container의 가장 앞에 있는 택배의 순번이 요청한 순번과 같을 경우 그 택배를 트럭에 싣는다. 이 반복문은 sub_container에 원소가 있는 동안 반복을 하며 매 시행시마다 sub_container내부에 꺼낼 수 없는 택배가 존재하는지 검사하고 꺼낼 수 없을 경우 실행을 종료하게 된다.

 

def solution(order):
    answer = 0
    main_container = list(range(1, len(order)+1))
    sub_container = []
    
    while order:
        while not sub_container:
            if main_container[0] == order[0]:
                main_container.pop(0)
                order.pop(0)
                answer += 1
            else:
                sub_container.insert(0, main_container[0])
                main_container.pop(0)

        while sub_container:
            if main_container and main_container[0] == order[0]:
                main_container.pop(0)
                order.pop(0)
                answer += 1
            elif sub_container[0] == order[0]:
                sub_container.pop(0)
                order.pop(0)
                answer += 1
            else:
                sub_container.insert(0, main_container[0])
                main_container.pop(0)
            if order and order[0] in sub_container and order[0] != sub_container[0]:
                return answer
    
    return answer

 

이 방법으로 테스트케이스는 모두 통과했지만 실행 시간 문제로 정답을 맞추지는 못했다. 전체적으로 코드를 개선할 필요가 있어보인다.

 

def solution(order):
    answer = 0
    main_container = list(range(1, len(order)+1))
    sub_container = []
    
    for o in order:
        while True:
            if main_container and not sub_container:
                if o == main_container[0]:
                    main_container.pop(0)
                    answer += 1
                    break
                else:
                    sub_container.insert(0, main_container[0])
                    main_container.pop(0)
            elif main_container and sub_container:
                if o == main_container[0]:
                    main_container.pop(0)
                    answer += 1
                    break
                elif o == sub_container[0]:
                    sub_container.pop(0)
                    answer += 1
                    break
                else:
                    sub_container.insert(0, main_container[0])
                    main_container.pop(0)
            elif not main_container and sub_container:
                if o == sub_container[0]:
                    sub_container.pop(0)
                    answer += 1
                    break
                else:
                    return answer

    return answer

 

 

약간 개선된 그 다음 코드, 복잡했던 조건들을 조건문 하나로 통합했다. 실행 시간이 약간 줄어서 정답률이 오르긴했지만 아직 많이 느리다.

 

from collections import deque

def solution(order):
    answer = 0
    main_container = deque(range(1, len(order)+1))
    sub_container = deque()
    
    for o in order:
        while True:
            if main_container and not sub_container:
                if o == main_container[0]:
                    main_container.popleft()
                    answer += 1
                    break
                else:
                    sub_container.appendleft(main_container[0])
                    main_container.popleft()
            elif main_container and sub_container:
                if o == main_container[0]:
                    main_container.popleft()
                    answer += 1
                    break
                elif o == sub_container[0]:
                    sub_container.popleft()
                    answer += 1
                    break
                else:
                    sub_container.appendleft(main_container[0])
                    main_container.popleft()
            elif not main_container and sub_container:
                if o == sub_container[0]:
                    sub_container.popleft()
                    answer += 1
                    break
                else:
                    return answer

    return answer

 

위의 방식을 그대로 활용하고 자료의 구조형을 deque로 바꿔주었다.

성공!

 

리스트의 원소들이 자주 변동되기 때문에 수정/삭제 속도가 빠른 deque로 바꾸니 알고리즘을 수정하지 않아도 실행시간이 매우 크게 단축되었다.