[프로그래머스] 햄버거 만들기(Python)

문제 링크

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

프로그래머스

소스 코드

def solution(ingredient):
    cnt = 0
    stack = []
    
    for exp in ingredient:
        stack.append(exp)
        # 지금까지 쌓인 재료가 4개 이상이고 뒤에서부터 4개로 햄버거가 될 때
        if len(stack) >= 4 and stack[-4:] == [1,2,3,1]:
            cnt += 1
            # 뒤에서 네 개를 pop
            for i in range(4):
                stack.pop()

    return cnt

오답(시간 초과)

def solution(ingredient):
    cnt = 0
    stack = []
    
    for idx in range(len(ingredient)):
        stack.append(ingredient[idx])
        if len(stack) >= 4 and stack[-4:] == [1,2,3,1]:
            stack = stack[:-4]
            cnt += 1

    return cnt

해설

• indexing, slicing의 시간복잡도에 대한 이해가 필요
• 로직 자체는 간단한 stack 유형

slicing

뭔가 논리 자체는 간단한 문제인데 문제에서 주어지는 리스트의 최대 길이가 1,000,000이라서 시간복잡도를 고려하지 않으면 절대로 통과할 수 없습니다.

기본적인 풀이 과정은 다음과 같습니다.

 

1) 리스트에서 원소를 하나씩 꺼내어 스택에 추가한다.

2) 스택의 뒤에서부터 네 개 원소가 햄버거로 완성이 되면 카운트를 올리고 네 개 원소는 없앤다.

 

리스트의 길이가 길기 때문에 문제가 발생할 수 있는 포인트는 슬라이싱에 있었습니다.

시간초과 판정을 받은 기존의 오답 풀이를 보면 stack = stack[:-4] 로 정의됩니다.

즉, 뒤에서부터 네 번째 이전의 모든 원소를 다시 stack으로 취합니다.

이는 리스트의 길이가 수십만 단위가 되었을 때는 분명 많은 시간이 소요되는 작업입니다.

 

따라서 문제 조건을 만족하는 경우,

슬라이싱하는 것이 아니라 리스트 전체 길이와 상관 없이 시간 복잡도가 O(1)인 pop을 네 번 수행하여 작업을 수행하는 데 걸리는 시간을 획기적으로 단축시킬 수 있습니다.

 

다섯 개의 테스트 케이스에 대한 코드 실행 시간을 아래 사진에서 확인할 수 있습니다.

리스트의 길이가 길수록 시간 차이가 압도적으로 발생하는 것이 눈에 확연히 띕니다.