[프로그래머스] lv.1 햄버거 만들기 python 풀이 시간초과 해결

문제

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

프로그래머스

 

문제 풀이

''.join으로 문자열 치환하여 find, index로 찾고 string[:idx] + string[idx+4:] 이런식으로 풀이하거나

리스트로 풀이하는데 리스트를 매번 + 연산을 통해 list[:idx] + list[idx+4:] 하면 시간초과 남.

stack을 쌓아가면서 뒤에서 4개의 원소만 확인하는 것이 이 문제의 핵심

 

cf) 파이썬에서 del 연산은 삭제한 후 뒤의 원소를 앞으로 땡겨줘야 하기 때문에 O(N)이고,

리스트 + 연산은 더하는 두 리스트의 길이에 따라 시간복잡도가 결정된다.

이 문제에서는 + 연산만 사용하지 않으면 된다.

 

코드

1) 리스트

def solution(ingredient):
    stack = []
    cnt = 0
    
    for i in ingredient:
        stack.append(i)
        if stack[-4:] == [1,2,3,1]:
            del stack[-4:]
            cnt += 1
            
    return cnt

 

2) 문자열

def solution(ingredient):
    stack = ''
    cnt = 0
    
    for i in ingredient:
        stack += str(i)
        if stack[-4:] == '1231':
            stack = stack[:-4]
            cnt += 1
            
    return cnt