23.05.01 -프로그래머스:햄버거 만들기

문제: 햄버거 만들기

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

프로그래머스

문제 설명: 입력으로 1,2,3으로 이루어진 수열이 리스트형태로 주어진다. 수열에서 부분수열 1,2,3,1 이 존재하면 햄버거 갯수가 1개 추가되고 수열에서 해당 부분수열이 제거된다. 이를 반복하여 최종 햄버거 갯수를 반환하면 된다.

 

시도 1: find 이용하기

주어진 입력으로부터 특정 패턴을 찾아내야하는 문제이다.

find는 문자열에서 특정 패턴이 존재하는지 확인하고 존재하면 해당 패턴의 첫번째 인덱스를 반환하는 메소드이다.

따라서 find를 이용하기 위해 입력을 문자열로 변환하고 문자열에서 '1231'을 찾아 그 부분만 인덱싱으로 제거하는 것을 더이상 '1231'이 발견되지 않을 때 까지 반복한다.

def solution(ings):
    answer = 0
    str_ingredient= ''.join(map(str,ings))
    while (i:=str_ingredient.find('1231')) != -1:
    	answer +=1
        str_ingredient=str_ingredient[:i] +str_ingredient[i+4:]
    return answer

이를 코드로 구현하면 위와 같다.

이 방식은 올바른 접근이긴 했다. 그러나 시간초과로 인해 통과하지 못했다.

 

시도 1 의 시간 복잡도

python의 find 메소드는 O(n*m)의 시간복잡도를 가진다. 따라서 while문안에서 find를 돌리므로 시간복잡도는 대략 O(n^2)이 된다. 이로인해  시간초과가 발생한 것이다.

 

해결: 유사 stack

문제에서 햄버거는 차곡 차곡 재료가 쌓이다가 가장 최근 재료들이 '1231'순으로 쌓여있으면 해당 재료들을 사용해 바로 만들어진다. 이는 stack의 동작과 유사하므로 이를 활용해보자.

반목문을 통해 입력 리스트로부터 재료를 스택에 차례대로 받아들인다. 재료를 받아들일 때 마다 가장 최근의 재료들이 1,2,3,1 순으로 쌓여있는지 확인하고 만약 그렇다면 재료들을 pop하고 햄버거 갯수를 1 더한다.

 

정답:

이를 코드로 구현하면 아래와 같다.

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