[프로그래머스] Lv2. 택배상자(by Python)

문제

코딩테스트 연습 - 택배상자 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

풀이

• 보조 컨베이어 벨트(코드에선 li)에 1부터 넣으면서, 제거할 것이 생기면(order 값이랑 같으면) while 반복문을 통해 제거
• 첫번째 while문은 order의 갯수만큼 반복
• 결국, order의 최종 인덱스가 답인걸 알 수 있음

 

처음 짠 코드는 왜 안됐을까?

• 그냥 단순히 보조 콘테이너에 값을 넣고, 빼는 방식으로 진행했다.
• visited를 둔 이유는, 이전에 제거한 숫자인지 확인하기 위해 추가했다.
• order의 길이가 최대 10^6인데 for문을 여러번 돌리니 당연히 시간초과 날 수밖에..
• 이런 레파토리 문제가 많이 보이는데, for문만 좋아하지 말고 while문을 최대한 활용해서 필요한 부분에만 반복문을 사용하자.

코드

 

처음에 푼 코드 - 테케 반절이 시간초과 났다.

from collections import deque

def solution(order):
    answer = 0
    idx = 0
    visited = [] 
    container = deque() 
    for i in order:
        if i in container and container:
            t = container.pop() 
            if t == i:
                answer += 1 
                visited.append(t)
            else:
                break
        else: 
            answer += 1
            visited.append(i)
            for j in range(1, i):
                if j not in visited:
                    container.append(j)  
  
    return answer

 

정답 코드

def solution(order): 
    answer = 0
    
    li = []
    i = 1
    idx = 0
    while i != len(order)+1: 
        li.append(i)
        while li and li[-1] == order[idx]:
            idx += 1
            li.pop() 
        i += 1 
    
    return idx