[알고리즘] 프로그래머스 택배상자 - Python

문제 : 프로그래머스 택배상자 문제

https://school.programmers.co.kr/learn/courses/30/lessons/131704

프로그래머스

 

문제에서 컨테이너를 설명하는 과정에서 "보조 컨테이너 벨트는 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어서 맨 앞의 상자만 뺄 수 있습니다. "라고 쓰여있었다. 이 문자을 보자마자 스택을 돌려서 표현한 것이라는 생각이 들었다. (백준의 스택 문제 중 유사한 문제가 있는거 같다.)

 

이 문제는 스택을 두 개 활용해야 했기 때문에 무작정 코드부터 쓰면 헷갈릴거 같았다. 그래서 먼저 코드 작성을 하기에 앞서서 변수와 스택이 여러개가 들어가기 때문에 정리를 해보았다. 

• prior 딕셔너리 : 각 택배가 트럭에 실어져야하는 순서 딕셔너리
• container 배열 : 메인 컨테이너 배열로 설정하였고, 여기서 만약 순서에 맞지 않는다면 보조 컨테이너로 뺄 수 있다. 스택으로 활용할 예정이다.
• sub_cont 배열 : 보조 컨테이너 배열이다. 메인과 마찬가지로 스택으로 활용할 예정이다.
• visit 딕셔너리 : 해당 인덱스의 택배가 메인과 보조 컨테이너 중 어디에 해당하는지 나타낸 딕셔너리이다. 편의상 메인에 있으면 True, 보조에 있으면 False로 설정했다.
• i 인덱스 : 트럭에 실어야하는 택배의 인덱스 

 

이 변수들을 바탕으로 구현한 코드는 아래와 같다. 

 

def solution(order):
    answer = 0
    prior={}
    container=[]
    sub_cont=[]
    visit={}
    i=1
    for i in range(len(order)):
        prior[order[i]]=i+1
        visit[order[i]]=True
   
    for i in range(len(order),0,-1):
        container.append(prior[i])
   
    while i<=len(order):
        if visit[i]:
            if container[-1]==i:
                container.pop()
                answer+=1
                i+=1
            else:
                sub_cont.append(container[-1])
                visit[container[-1]]=False
                container.pop()
        elif sub_cont[-1]==i:
            sub_cont.pop()
            answer+=1
            i+=1
        else:
            break
    
    
    return answer

 

while 반복문 안에 조건이 많아서 읽기 어려운 점이 조금 아쉽다.

 

반복문을 설명하자면 먼저 트럭에 실어야 하는 인덱스의 택배가 메인과 보조 컨테이너 중 어디에 해당하는지 파악한다. 그 후 메인에 있다면 conatiner 스택에서 top 원소와 비교를 한다. top 원소와 같을 때는 그대로 pop을 하고 인덱스와 answer를 증가하면 된다. 반면 top 요소와 다를 때는 top 요소를 빼내서 보조 컨테이너로 옮겨준다.

 

만약 인덱스에 해당하는 택배가 보조 컨테이너에 위치한다면 top 원소와 비교를 해보고 같으면 answer와 인덱스 증가, 다르면 바로 반복문을 중단한다. 왜냐하면 container는 스택이기 때문에 top 원소를 제거하지 않고는 그 안의 요소를 꺼내지 못하기 때문이다. 

 

이렇게 시간 복잡도는 O(n)으로 시간 초과 없이 해결할 수 있었다.