[프로그래머스/Python] Level2 - 택배상자

 💬 문제

 

🔨 입출력 예

  

 

 

💡 해결

큐와 스택을 사용하는 자료구조 문제로 너무 직관적이었다. 처음에 큐를 써야 될까? 라는 생각이 들었지만 직관적으로 큐와 스택을 사용하여 풀기로 하였다.

from collections import deque

def solution(order):
    n = len(order)
    now = 0
    arr = deque()
    stack = []
    result = 0
    
    for i in range(n):
        arr.append(i+1)
    
    while True:
        if len(arr) == 0 and (len(stack) ==0 or stack[-1] != order[now]):
            return result
        
        if len(arr) >0:
            tmp = arr[0]
        else:
            tmp = -1
        
        if tmp == order[now]:
            arr.popleft()
            now+=1
            result+=1 
        elif len(stack) !=0 and stack[-1] == order[now]:
            stack.pop()
            now+=1
            result+=1
        else:
            arr.popleft()
            stack.append(tmp)

그렇게 직관적으로 푼 코드이다. 문제에서 보내준 제한 조건을 따라가며, 갈 수 있는 방향은 총 3개이다.

1. 컨테이너에서 배송지

2. 컨테이너에서 서브컨테이너(스택)

3. 서브 컨테이너(스택)에서 배송지

 

이렇게 제한조건이 밑에 3개들이고, 그 위에는 탈출 조건들이다. 그런데, 사실 3번인가 테케를 틀렸었다.

list out of bound 에러가 많이 떴었고,  맨 위 탈출 조건을 3번이나 고쳤다. 안좋은 코드인거다.

어떻게든 맞추긴 했는데, 훨씬 더 줄일 수 있을거 같은데 좋은 방법이 생각이 안나 다른사람들의 코드를 보았다.

 

큐를 쓰지 않고, 인덱스를 이용하여 풀면 시간을 더 줄일 수 있었고,

컨테이너에서 배송지로 바로 가는 것을 스택을 거쳐 간다면 1,2,3 중에서 1,2를 없애고 3만 볼 수 있었다.(똑똑한 사람들)

 

그렇게 밑이 최종 코드이다.

👨🏻‍💻  CODE
 

def solution(order):
    answer = 0
    stack = []
    idx=1 
    
    while idx != len(order)+1:
        stack.append(idx)
        while stack[-1] == order[answer]:
            answer += 1
            stack.pop()
            if len(stack) == 0:
                break
        idx += 1
    return answer

 

 

💪🏻 느낀점

 

저런 구상을 내가 코테때 할 수 있을까 걱정된다.