[알고리즘] 프로그래머스 햄버거 만들기 - Python

문제 : 프로그래머스 햄버거 만들기 문제

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

프로그래머스

 

 

이 문제는 기본적인 스택 문제인데  너무 복잡하게 접근을 했던거 같다. ingredient 리스트에서 가장 끝부분부터 [1,2,3,1]을 비교해가며 pop을 했으면 되는 간단한 문제였다.

 

나의 풀이도 스택을 활용하기는 하였으나 index를 보관하는 용도로 사용했다. 

def solution(ingredient):
    answer = 0
    idx=0
    order=[1,2,3,1]
    lst=[]
    for i in ingredient:
        if i==1 and idx!=3:
            if idx!=0:
                lst.append(idx)
            idx=1
        elif i==order[idx]:
            if idx==3:
                answer+=1
                if len(lst)>0:
                    idx=lst[-1]
                    lst.pop()
                else:
                    idx=0
            else:
                 idx+=1
        else:
            idx=0
            lst=[]
    return answer

 

ingredient를 반복문으로 돌아가면서 1이 등장했을 때부터 추적을 해나가는 방식이다. 만약 1이 나왔다면 그 시점부터 idx를 1로 두고, 기존 idx는 lst에 저장을 해두는 방식이다. 코드도 그렇고 로직도 굉장히 복잡했다. 이 부분을 개선하려고 다른 사람들의 풀이를 찾아보니 매우 단순하게 구현을 한 것을 볼 수 있었다. 아래와 같이 ingredient의 끝부분부터 비교해나가면 되었던 것이다. 다시 풀어본 풀이는 아래와 같다. 

 

def solution(ingredient):
    answer = 0
    stk=[]
    for i in ingredient:
        stk.append(i)
        if len(stk)>=4:
            if stk[-1]==1 and stk[-2]==3 and stk[-3]==2 and stk[-4]==1:
                answer+=1
                stk.pop()
                stk.pop()
                stk.pop()
                stk.pop()
            
    return answer

 

이 방법은 stk에 재료들을 하나씩 추가해나가면서 stk의 끝 요소들부터 만족하는지 파악해나가는 방법이다. 나의 풀이보다 간단하고 보기도 쉽다. 문제를 풀기 전에 한번 더 깊이 생각하도록 해야겠다..