[프로그래머스] 햄버거 만들기

문제 링크:

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

회고:

• 풀이 방법 (stack)
  1. 재료를 나타내는 배열을 순회하면서, 현재까지의 재료를 스택에 쌓는다.
  2. 스택에 쌓인 재료들을 확인하여 정해진 햄버거 구성 순서와 일치하는지 검사한다.
  3. 만약 스택의 상위 재료들이 햄버거 구성 순서와 일치한다면, 해당 재료들을 스택에서 제거하고 햄버거를 1개 포장한 것으로 간주한다.
  4. 모든 재료를 순회할 때까지 위 과정을 반복한다.
  5. 포장된 햄버거 총 개수를 반환한다.
• 해당 문제는 효율성을 따진다.
  - 시간 복잡도: O(n)
  - 공간 복잡도: O(n)
  
  

python

def solution(ingredients):
    # 햄버거 구성 순서
    bugger_pattern = [1, 2, 3, 1]
    stack = []
    count = 0

    for num in ingredients:
        # 스택에 재료 쌓음
        stack.append(num)

        # 스택에 쌓인 재료가 햄버거 구성 순서와 일치하는지 확인
        if len(stack) >= len(bugger_pattern) and stack[-len(bugger_pattern):] == bugger_pattern:
            # 햄버거 구성과 일치하면 스택에서 해당 재료들 제거
            for _ in range(len(bugger_pattern)):
                stack.pop()

            # 햄버거 카운트 증가
            count += 1

    return count


if __name__ == "__main__":
    result = solution([1, 1, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1])

    print(result)
    print(result == 3)

3
True