본문 바로가기
코딩테스트/프로그래머스

프로그래머스 | Python | stack, 자료구조 | 햄버거 만들기 (Lv.1)

by RuntimeSimple 2025. 2. 27.

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

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

이 문제는 스택을 활용하여 연속된 패턴을 찾아내고 이를 제거하면서 햄버거의 개수를 세는 문제입니다. 핵심은 "빵-야채-고기-빵"이라는 정해진 패턴을 빠르게 감지하고 처리하는 것입니다.


코드

def solution(ingredient):
    stack = []
    answer = 0
    target = [1, 2, 3, 1]  # 햄버거 패턴

    for item in ingredient:
        stack.append(item)  # 스택에 재료를 추가
        # 스택 길이가 4 이상일 때만 슬라이싱 수행
        if len(stack) >= 4 and stack[-4:] == target:
            answer += 1
            del stack[-4:]  # 햄버거 패턴 제거

    return answer

코드 해설

  1. 스택을 활용한 재료 추가
    •   stack.append(item)으로 재료를 순서대로 추가합니다.
    •   스택은 재료를 쌓아 올리듯이 처리할 수 있는 자료구조입니다.
  2. 햄버거 패턴 감지
    •   stack[-4:] == [1, 2, 3, 1]를 통해 마지막 4개의 재료가 햄버거 패턴인지 확인합니다.
    •   패턴이 일치하면 answer를 1 증가시키고, del stack[-4:]로 해당 패턴을 스택에서 제거합니다.
  3. 결과 반환
    •   모든 재료를 처리한 뒤, answer에 저장된 값(포장된 햄버거 개수)을 반환합니다.

핵심 아이디어

  • 스택 사용 이유
    •   재료가 순서대로 쌓이기 때문에 마지막 4개의 재료를 확인하면 즉시 패턴을 감지할 수 있습니다.
    •   리스트 슬라이싱(stack[-4:])은 효율적으로 마지막 4개의 원소를 확인합니다.
  • 시간 복잡도
    •   리스트의 길이가 최대 1,000,000이므로, 효율적인 처리가 필요합니다.
    •   스택을 사용하여 한 번의 순회로 해결하기 때문에 시간 복잡도는 O(n)입니다.
  • 출제 의도
    •   스택을 활용한 패턴 탐지와 리스트의 기본 연산 이해를 평가하려는 문제입니다.

예제 흐름

예제 입력

ingredient = [2, 1, 1, 2, 3, 1, 2, 3, 1]

코드 실행 흐름

초기 상태

  •   stack = []
  •   answer = 0
  •   target = [1, 2, 3, 1]

첫 번째 재료 추가 (item = 2)

  •   stack.append(2)
  •   stack = [2]
  •   마지막 4개: stack[-4:] = [2] (길이 4 미만, 비교 안 함)
  •   No match → answer = 0

두 번째 재료 추가 (item = 1)

  •   stack.append(1)
  •   stack = [2, 1]
  •   마지막 4개: stack[-4:] = [2, 1] (길이 4 미만, 비교 안 함)
  •   No match → answer = 0

세 번째 재료 추가 (item = 1)

  •   stack.append(1)
  •   stack = [2, 1, 1]
  •   마지막 4개: stack[-4:] = [2, 1, 1] (길이 4 미만, 비교 안 함)
  •   No match → answer = 0

네 번째 재료 추가 (item = 2)

  •   stack.append(2)
  •   stack = [2, 1, 1, 2]
  •   마지막 4개: stack[-4:] = [2, 1, 1, 2]
  •   No match → answer = 0

다섯 번째 재료 추가 (item = 3)

  •   stack.append(3)
  •   stack = [2, 1, 1, 2, 3]
  •   마지막 4개: stack[-4:] = [1, 1, 2, 3]
  •   No match → answer = 0

여섯 번째 재료 추가 (item = 1)

  •   stack.append(1)
  •   현재 스택: stack = [2, 1, 1, 2, 3, 1]
  •   마지막 4개: stack[-4:] = [1, 2, 3, 1]
  •   Match found!
    •   stack[-4:] == target (햄버거 패턴 [1, 2, 3, 1]과 일치)
    •   answer += 1 → answer = 1
    •   del stack[-4:] (마지막 4개 제거)
    •   Updated stack: stack = [2, 1]

일곱 번째 재료 추가 (item = 2)

  •   stack.append(2)
  •   stack = [2, 1, 2]
  •   마지막 4개: stack[-4:] = [2, 1, 2] (길이 4 미만, 비교 안 함)
  •   No match → answer = 1

여덟 번째 재료 추가 (item = 3)

  •   stack.append(3)
  •   stack = [2, 1, 2, 3]
  •   마지막 4개: stack[-4:] = [2, 1, 2, 3]
  •   No match → answer = 1

아홉 번째 재료 추가 (item = 1)

  •   stack.append(1)
  •   stack = [2, 1, 2, 3, 1]
  •   마지막 4개: stack[-4:] = [1, 2, 3, 1]
  •   Match found!
    • stack[-4:] == target
    • answer += 1 → answer = 2
    • del stack[-4:]
    • Updated stack: stack = [2]

최종 결과

  • 포장된 햄버거 개수: answer = 2

한 줄 요약

스택을 이용해 "빵-야채-고기-빵" 패턴을 효율적으로 탐지하고 제거하여 포장할 수 있는 햄버거의 개수를 계산하는 문제입니다.


여기서 잠깐!

Python에서 리스트의 요소를 삭제하는 두 가지 방법 : remove와 del 에 대해 더 알아봅시다.

1. remove

  • 목적: 리스트에서 특정 을 찾아 삭제합니다.
  • 사용법: list.remove(value)
  • 특징:
    •   리스트에서 첫 번째로 발견되는 값만 삭제합니다.
    •   값이 존재하지 않으면 ValueError가 발생합니다.
    •   리스트의 길이를 줄입니다.

예시:

lst = [1, 2, 3, 2, 4]
lst.remove(2)  # 첫 번째 2를 제거
print(lst)  # [1, 3, 2, 4]

2. del

  • 목적: 리스트의 특정 인덱스슬라이스를 삭제합니다.
  • 사용법:
    •   del list[index] 또는
    •   del list[start:end] (슬라이싱)
  • 특징:
    •   값이 아닌 인덱스로 요소를 삭제합니다.
    •   슬라이싱을 사용하면 한 번에 여러 요소를 삭제할 수 있습니다.
    •   리스트를 완전히 삭제하려면 del list로 사용할 수도 있습니다.
    •   인덱스가 범위를 벗어나면 IndexError가 발생합니다.

예시:

lst = [1, 2, 3, 4]
del lst[1]  # 인덱스 1 요소 삭제
print(lst)  # [1, 3, 4]

lst = [1, 2, 3, 4]
del lst[1:3]  # 인덱스 1~2 요소 삭제
print(lst)  # [1, 4]

차이점 비교

 

구분  remove  del
삭제 기준 값을 기준으로 삭제 인덱스 또는 슬라이스를 기준으로 삭제
대상 첫 번째로 발견된 값 특정 인덱스(또는 범위)의 값
에러 조건 값이 없으면 ValueError 발생 인덱스가 범위를 벗어나면 IndexError 발생
사용 범위 리스트에서만 사용 가능 리스트 외에도 변수 삭제 가능

언제 사용해야 할까?

  • 값으로 삭제: 특정 값(예: 2)을 삭제하려면 remove를 사용하세요.
  • 인덱스로 삭제: 특정 위치의 값을 삭제하거나 슬라이싱을 사용할 때는 del을 사용하세요.

예시 비교:

lst = [1, 2, 3, 2, 4]

# remove: 값으로 삭제
lst.remove(2)  # 첫 번째 2 삭제
print(lst)  # [1, 3, 2, 4]

# del: 인덱스로 삭제
del lst[1]  # 인덱스 1 삭제
print(lst)  # [1, 2, 4]