프로그래머스 Lv1 햄버거 만들기 (python)

햄버거 만들기

풀이

처음에 일단 부딪히는 방법으로 풀어서 아래처럼 풀었다.

# 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓임.
# 순서에 맞게 햄버거를 완성시켜야함
# 햄버거는 아래서부터 빵-야채-고기-빵, 1-2-3-1.
# 포장하는 동안 재료가 추가적으로 돌어오진 않음

def solution(ingredient):
    burger_num = 0
    burger = [1,2,3,1]
    while len(ingredient) >= 4:
        for i in range(len(ingredient)-3):
            if ingredient[i:i+4] == burger:
                burger_num += 1
                ingredient = ingredient[:i] + ingredient[i+4:]
                break
        else:
            break    
    return burger_num

풀리기는 하지만, 시간 초과가 나는 단점이 있었다.
그래서 어떻게 해야 시간을 조금이나마 줄일 수 있을까 해서 하다가
stack을 이용한 방법으로 풀어보자 생각했다.
그래서 아래처럼 풀었다.

stack을 쓰면서 시간을 조금이라도 줄이고자, append pop 대신 top을 이용해서 풀이를 했다.

# 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓임.
# 순서에 맞게 햄버거를 완성시켜야함
# 햄버거는 아래서부터 빵-야채-고기-빵, 1-2-3-1.
# 포장하는 동안 재료가 추가적으로 돌어오진 않음

def solution(ingredient):
    burger_num = 0
    burger = [1,2,3,1]
    # stack
    stack = [0]*len(ingredient)
    top = -1
    for i in range(len(ingredient)):
        top += 1
        stack[top] = (ingredient[i])
        # 탑이 3일 때 즉, 갯수가 4개 이상 쌓였을 경우만 비교
        if top >= 3 and stack[top-3] == 1 and stack[top-2] == 2 and stack[top-1] == 3 and stack[top] == 1:
            burger_num += 1
            top -= 4
    return burger_num

그러니 시간은 아래처럼 나오면서 해결되었다.

다른 사람 풀이

이런 것을 보니, 나 혼자 어려운 길로 가고 있던 느낌이다....
그냥 재료 쌓아 올리면서 1,2,3,1이 생기면 pop으로 다 빼버린다....
내 거보다 더 빠르다 흑....
난 언제 똑똑해지려나.

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