문제

문제 링크

코드

from collections import deque

def solution(order):
    answer = 0
    
    q = deque(order)
    sub = []
    box = 1
    while q:
        # 박스를 바로 실는 경우
        if box == q[0]:
            q.popleft()
            answer += 1
            box += 1
        # 서브 컨테이너 밸트에서 실는 경우
        elif sub and sub[-1] == q[0]:
            sub.pop()
            q.popleft()
            answer += 1
        # 서브 컨테이너에 박스를 넣는 경우
        elif box < q[0]:
            sub.append(box)
            box += 1
        # 더 이상 실을 수 없는 경우
        elif box != q[0] and sub and sub[-1] != q[0] and box > sub[-1]:
            break
    
    return answer

분석

이 문제는 각각의 행위에 대한 조건을 찾는게 포인트였다. 내가 찾기 어려웠던 조건은 서브 컨테이너 밸트에 실는 조건이었다. 그래서 아래와 같이 작은 스케일에서 법칙을 찾아보고자 했다.

    박스 1
    택배기사
    보조 1
    
    박스 2
    택배기사
    보조 1 2
    
    박스 3
    택배기사
    보조 1 2 3
    
    박스 4
    택배기사 4
    보조 1 2 3
    
    박스 5
    택배기사 4 3
    보조 1 2 

여기서 보면 5에서 종결이 되었다. 그런데 사실 5에서 끝내지 않고 서브 컨테이너 밸트에 넣는 선택지가 있었는데도 종결이 되었다. 이는 곧 박스의 수가 다음에 실을 박스보다 크기가 작을 때만 서브 컨테이너 밸트에 넣기 때문이다. 이를 통해 서브 컨테이너 밸트에 넣는 조건을 알게 되었다.

사용한 자료구조

1. 스택 : 서브 컨테이너 밸트와 입출력 방식이 같다.
2. 큐 : 택배기사가 정해놓은 순서와 입출력 방식이 같다.

깨달은 점

1. 입출력 방식을 통해 자료구조 선택
2. 규칙을 못 찾겠으면 작은 스케일에서 찾아볼 것.
   • 근데 순차적인 관찰이 중요할 때가 있고, 함축적인 수학 규칙을 찾는게 중요할 때가 있다. 즉, 순차적인 관찰을 해도 규칙이 안찾아지면 바로 정수론적인 접근을 해야 한다.
3. 귀납 추론을 위해 관찰을 할 때 규칙
   a. 순열로서 수를 관찰한다.
   b. 그래도 규칙을 못 찾겠으면 정수론적인 접근을 한다.