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

 

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

프로그래머스

 

(실패)

입력 받은 배열을 스트링으로 바꿔서 '1231'이 포함되었을 때 그 부분을 제거하고 정답의 개수를 하나 추가했다.

하지만 이런 식으로 문제를 풀면 원소들을 제거하는 함수의 시간 복잡도 때문에 시간 초과가 발생한다고 한다.

# 프로그래머스 133502: 햄버거 만들기 

def solution(ingredient):
    answer = 0
    ingredient = ''.join(str(i) for i in ingredient)

    while '1231' in ingredient:
        answer += 1
        ingredient = ingredient.replace('1231', '', 1) # 맨 앞의 기호만 교체 

    return answer

 

(성공)

따라서 시간 초과를 방지하기 위해 문자열을 하나 더 선언해서 ingredient의 값을 하나씩 넣어주고,

맨 끝의 문자열이 '1231'일 때 뒤에서 4개의 문자열을 지우고 정답의 개수를 하나 추가했다.

# 프로그래머스 133502: 햄버거 만들기

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

    return answer

 

** 추가한 테스트 케이스 **

input) [1, 1, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1]

output) 3

 

input) [2, 1, 2, 3, 1, 2, 3, 1, 1]

output) 1