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

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

프로그래머스

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

---

코드

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]