[프로그래머스][PYTHON] Lv. 1 햄버거 만들기

문제 설명

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

프로그래머스

 

내 풀이 (오답)

처음에는 주어진 리스트를 문자열로 바꿔서, 햄버거를 만들 수 있는 문자를 제거하려 했다. 

# 빵 – 야채 – 고기 - 빵 (1, 2, 3 -> 빵, 야채, 고기)
def solution(ingredient):
    answer = 0
    # 햄버거를 만드는 순서는 1 -> 2 -> 3 -> 1
    ham = '1231'
    
    # 주어진 리스트를 string으로 변경([2, 1, 1] -> '211')
    ingredient = list(map(str, ingredient))
    ingredient = ''.join(ingredient)
    
    # 문자열에서 '1231'을 찾을 수 있으면..
    while ingredient.find(ham) > 0:
        # 1231을 제거 -> 더 이상 찾을 수 없을 때까지 반복
        ingredient = ingredient.replace(ham, '')
        answer += 1
    return answer

 

이 풀이의 경우 예제 케이스에 대해서는 정답이 나지만, 실제 테스트 케이스에 대해서는 22점 밖에 나오지 않는다. 

 

1. ingredient 배열을 문자열로 변환하는 부분의 시간 복잡도 = O(n)

ingredient = list(map(str, ingredient))
ingredient = ''.join(ingredient)

 

2. 문자열에서 '1231'을 찾는 부분의 시간 복잡도 = O(n^2)

while ingredient.find(ham) > 0:
    ingredient = ingredient.replace(ham, '')
    answer += 1

 

이 부분에서 find() 메서드는 최악의 경우 O(n)의 시간 복잡도를 가진다.

또한, replace() 메서드 역시 최악의 경우 O(n)의 시간 복잡도를 가진다. 

이를 루프 내에서 반복하기 때문에 최악의 경우 O(n^2)의 시간 복잡도를 가지게 된다. 

 

 

다른 사람 풀이 (정답)

마땅한 방법이 떠오르지 않아 다른 사람의 풀이를 보고 해결해보았다. 

아래는 스택을 이용하여 각 재료를 순차적으로 처리하는 풀이이다. 

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

 

먼저, 햄버거의 속 재료가 쌓이는 것처럼 각 재료를 스택에 하나씩 추가한다. 

이러한 스택의 마지막 4개 요소가 햄버거를 만들 수 있는 배열 [1, 2, 3, 1]과 같으면, 

del 함수를 이용해 이 요소를 제거한다. 

스택에 원소를 추가할 때 시간 복잡도는 O(1)이며, 

del을 이용해 원소를 제거하는 시간 복잡도 역시 O(1)이다. 

 

 

 

동일한 방법이지만, pop()을 사용할 수도 있다. 

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

 

 

시간 복잡도 정리

https://velog.io/@kim_min_hyuk/Python-%EC%9E%90%EB%A3%8C%ED%98%95%EB%B3%84-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EC%A0%95%EB%A6%AC

Python 자료형별 시간 복잡도 정리

 

시간 복잡도에 대한 설명을 자세히 정리해둔 블로그가 있어 함께 남겨본다!