택배상자

풀이

문제를 보고 큐와 같이 스택으로 풀어야겠다라고 생각을 했다.
그래서 메인 컨테이너와 보조 컨테이너로 생성하고, 메인 컨테이너에서 꺼내서, 보조컨테이너와 같이 비교하는 방법을 사용했다.
그것이 아래 코드이다.

# 영재 상하차함.
# 택배상자는 크기가 모두 같음
# 1번 상자부터 n번 상자까지 순서대로 전달됨
# 하차 1번부터 가능, 택배 기사가 알려준 순서에 맞게 택배상자를 상차해야함
# 아직 순서 아닌 상자는 보조 컨테이너 벨트(앞뒤로 이동 가능) 맨 앞의 상자만 뺄 수 있음
# 보조 컨테이너 벨트는 stack임
# !!! 보조 컨테이너 벨트를 이용해서 기사가 원하는 순서대로 상자를 싣지 못 한다면, 더 이상 상자를 싣지 않음
# 상자 컨테이너는 Q, 보조 컨테이너는 stack
def solution(order):
    # 주 벨트는 Q 형태로 1번~ 끝번까지 존재함
    main_belt = [ x for x in range(1, len(order) + 1)]
    # 보조 벨트는 stack 형태로 존재함 append와 pop()을 이용해보자
    sub_belt = [0]
    # 기사가 원하는대로 적재한 박스 갯수
    can_box = 0
    # 컨테이너 작동!
    i = 0
    while i < len(order):
        # order[i]가 주 벨트에서 온 상자와 같거나 보조 벨트에서 뽑을 수 있는 상자와 같다면
        if (sub_belt and order[i] == sub_belt[-1]) or (main_belt and order[i] == main_belt[0]):
            # 주벨트와 같으면
            if main_belt and order[i] == main_belt[0]:
                main_belt.pop(0)
            # 보조벨트와 같으면    
            else:
                sub_belt.pop()
            can_box += 1
            # 해치웠으니 다음 order를 확인하자
            i += 1

        # 아니 이 상자가 아니라니!
        else:
            # 아직 주 벨트에 상자가 남아있으면 보조로 넘기기
            if len(main_belt) > 0:
                tmp = main_belt.pop(0)
                sub_belt.append(tmp)
            # 주 벨트에도 없으면?!
            else:
                break
                
    return can_box

이렇게 하니 풀리긴 풀리는데 시간이 너무 오래 걸려서 시간 초과가 나버렸다.
그래서 우야노...하다가 그냥 stack만 써도 된다는 것을 깨닫고 아래처럼 풀었다.

1. for문을 1번부터 len(order)까지 순회하도록 생성한다.(박스번호로 이용)
2. sub_container에 일단 넣는다.
3. sub_container를 while문을 이용해 stack형식으로 탐색한다.(꺼낼 수 있는 값이 order값과 같으면 꺼내서 적재하고, 아니면 넘어가고)
4. 2번과 3번을 반복하다 종료되면, 적재한 박스 수량을 반환한다.

# 보조 컨테이너에 다 넣은 후에 확인하기
def solution(order):
    load_box = 0
    sub_container = []
    turn = 0
    # 1번 박스부터 n번 박스까지 컨테이너타고 옴
    for i in range(1, len(order)+1):
        # 보조 컨테이너에 넣기
        sub_container.append(i)
        # 보조 컨테이너에 값이 있으면 계속 확인
        while sub_container:
            if sub_container[-1] == order[turn]:
                load_box += 1
                turn += 1
                sub_container.pop()
            else:
                break
    return load_box

다른 사람 풀이

음.. 내가 푼 방법과 동일하다고 보면 되겠다.

def solution(order):
    answer = 0
    stacks = []
    N = len(order)
    i = 1
    idx = 0
    while i < N+1:
        stacks.append(i)
        while stacks[-1] == order[idx]:
            idx += 1
            stacks.pop()
            if len(stacks) == 0:
                break
        i += 1


    return idx