99클럽 코테 스터디 9일차 TIL - 획기적인 풀이는 이해하고 넘어가자

문제 - 택배상자 문제링크

 

오늘 배운 점

스택의 활용도는 무궁무진하고 어렵습니다.
획기적인 풀이가 답이 될 수 있는 이유를 알고 넘어가는건 재밌습니다.
 

문제 설명

메인 컨베이어 벨트에 1부터 n의 번호가 달린 상자가 n,n-1,...3,2,1 이런식으로 정렬되어 왼쪽에서 오른쪽으로 이동하고 있습니다.
그리고, 택배원은 자기가 생각한 순서대로 상자를 트럭에 실어야 합니다.
택배원은 보조 컨베이어벨트에 상자를 차곡차곡 옮길 수도 있습니다.
보조 컨베이어벨트는 스택같은 LIFO 구조라고 보면 됩니다.
이때 택배원은 최대 몇개의 상자를 트럭에 실을 수 있는지 구하는 문제입니다.

 

풀이 과정

세 가지 경우로 나누어 풀이했습니다.
1. 메인 컨베이어 벨트의 맨 앞 상자가 자신이 처리해야 하는 상자와 같을 때
2. 보조 컨베이어 벨트의 맨 앞 상자가 자신이 처리해야 하는 상자와 같을 때,
3. 둘 다 아니면 메인 컨베이어 벨트 맨 앞 상자를 보조 컨베이어에 옮기고, 만약 메인에 상자가 없을 시 종료
 

def solution(order):
    st1 = [num for num in range(len(order), 0, -1)]
    st2 = []
    
    idx = 0
    while True:
        if st1 and st1[-1] == order[idx]:
            st1.pop()
            idx += 1
            continue
            
        elif st2 and st2[-1] == order[idx]:
            st2.pop()
            idx += 1
            continue
        
        if st1:
            st2.append(st1.pop())
        else:
            break
            
    return idx

 
컨베이어는 스택으로 구현했고, 메인 st1의 초깃값 세팅을 해주었습니다. 이후 3가지 경우로 나누어 로직을 작성하였습니다.
 

획기적인 풀이

제출된 답 중 코드가 아주 간단한 풀이를 발견했습니다.

"""
    일반적: 메인에 있는지, 메인에 없으면 보조에 있는지, 보조에 없으면 메인에서 보조로 옮기기, 메인이 비어있으면 끝
    최적화: 무조건 보조 컨테이너에 옮기고 판단하고 옮기고 판단하고
    
"""
def solution(order):
    cnt = 0
    st = []
    for idx in range(len(order)):
        st.append(idx + 1)
        
        while st and st[-1] == order[cnt]:
            st.pop()
            cnt += 1
    return cnt

 
위 코드를 처음 봤을 때는, 메인 컨베이어를 확인하는 부분이 없는데 어떻게 정답일 수 있는걸까 라는 의문이 있었습니다. 보조 컨베이어 st의 마지막 원소와 현재 실어야 하는 상자만 비교했기 때문입니다.
하지만 정답일 수 있었던 이유는 for문을 돌 때마다 무조건 idx + 1을 st에 넣어주기 때문에 메인 맨 앞에 애초에 있었으면 보조로 이동된 후 처리되고, 맨 앞에 없었으면 그대로 메인의 다음 상자를 실으러 다음 idx로 가게 됩니다.
메인에서 보조로 이동 후, order[cnt]와 같지 않아 보조의 맨 앞에 추가된 상자로 인해 바로 전 상자가 처리되지 않을 경우는 없습니다. 애초에 메인쪽 상자가 이동되기 전 while 문을 통해 보조쪽 상자와 매칭을 하기 때문입니다.

 

총평

스택은 자료구조는 간단한데 응용이 무궁무진한 것 같습니다.