프로그래머스, 택배상자(python)

문제 설명

1번부터 n번까지 번호가 붙은 상자가 컨테이너에 놓여 있다. 영재는 순서대로 컨테이너에서 상자를 가지고 와 트럭에 을 수 있다. 그러나 트럭에 실을 수 있는 택배에는 순서가 있어 순서가 안 된 택배를 가지고 오면 이를 보조 컨베이터 벨트에 둔다. 보조 컨베이어 벨트는 오로지 맨 앞에서만 택배를 넣었다가 뺄 수 있다.

 

만일 영재가 더이상 택배를 주어진 순서대로 실을 수 없다면 종료한다. 

 

총 몇 개의 상자를 연재가 실을 수 있는지 구하는 문제다.

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

프로그래머스

문제 풀이

일단 order의 최대 길이가 1,000,000이므로 2차 반복문을 사용할 경우 시간초과가 날 수 있어 1차 반복문만을 이용하여 풀어야 한다. 

 

나는 반복문의 기준을 box로 잡았다. 그래서 box의 크기가 order보다 커질 경우 탈출하는 구문을 반복문 제일 첫 번째에 작성했다. 

 

current는 현재 내가 비교 하고 싶은 순서의 박스를 담는 변수이다.

 

만일 current와 box가 같아 보조 컨테이너까지 갈 필요가 없는 경우 idx(order의 값을 지정하는 인덱스)와 answer, box를 하나씩 늘려준다.

 

current와 box가 다르면 보조 컨테이너에서 제일 앞에 맞는 박스가 있는지 찾아야 한다.

먼저 보조 컨테이너의 크기가 0인지 아닌지를 확인한다. 0이 아니면 박스가 있다는 의미이므로 제일 앞에 있는 박스를 확인한다. 만일 제일 앞에 현재 순서인 박스가 있다면 pop을 해서 박스를 하나 빼주고 answer와 idx에 1을 더해준다. 이때 조심해야 할 게 있는데 박스에도 1을 더해주면 안 된다는 것이다.

 

왜냐하면 우리는 단순히 current와 현재 box를 비교만 해줬을 뿐 현재 box를 가지고 뭘하지는 않았기 때문이다. 그러니까 현재 작업은 현재 박스가 현재 순서와 같지 않아서 보조 컨테이너를 확인하는 것이다. 때문에 박스를 하나 늘리지 말고 다음 순서로 넘어가야지 현재 박스를 기준으로 다시 작업을 할 수 있는 것이다.

 

예를 들어서 순서가 2번이라고 하자.

그런데 컨테이너에서 꺼낼 수 있는 박스는 4여서 보조 컨테이너를 확인해야 한다.

다행히 보조 컨테이너에서 꺼낼 수 있는 박스는 2이기에 순서와 맞아 떨어진다.

그러면 박스 2를 보조 컨테이너에서 꺼내서 트럭에 싣는다.

 

여기서 잠깐!!!

그리고 컨테이너에서 선택할 박스의 숫자를 하나 높여보자. 박스의 숫자는 5가 되는데, 이렇게 되면 박스 4를 실행하지 않게 된다. 그러므로 박스 숫자를 높여서는 안 되는 것이다.

 

이와는 반대로 보조 컨테이너의 첫 값과 current가 다르면 box를 보조 컨테이너에 넣어준다. 또한 길이가 0이여도 현재 box를 보조 컨테이너에 넣어준다.

 

맨 마지막으로 보조 컨테이너에 남아있는 박스들을 현재의 순서와 하나씩 비교해서 맞으면 꺼내주고 아니면 탈출한다.

 

코드

python

def solution(order):
    answer = 0
    idx = 0
    box = 1
    tmp = []
    
    while True:
        if box > len(order):
            break
        
        current = order[idx]
        
        if current == box:
            idx += 1
            answer += 1
            box += 1
        elif current != box:
            if len(tmp) != 0:
                if tmp[-1] == current:
                    tmp.pop()
                    answer += 1
                    idx += 1
                else:
                    tmp.append(box)
                    box += 1
            elif len(tmp) == 0:
                tmp.append(box)
                box += 1
    
    for i in range(idx, len(order)):
        if tmp[-1] == order[i]:
            tmp.pop()
            answer += 1
        else:
            break
        
        
    return answer