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
코드 해설
- 스택을 활용한 재료 추가
- stack.append(item)으로 재료를 순서대로 추가합니다.
- 스택은 재료를 쌓아 올리듯이 처리할 수 있는 자료구조입니다.
- 햄버거 패턴 감지
- stack[-4:] == [1, 2, 3, 1]를 통해 마지막 4개의 재료가 햄버거 패턴인지 확인합니다.
- 패턴이 일치하면 answer를 1 증가시키고, del stack[-4:]로 해당 패턴을 스택에서 제거합니다.
- 결과 반환
- 모든 재료를 처리한 뒤, 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]
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
프로그래머스 | Python | Brute Froce | [PCCE 기출문제] 9번 / 이웃한 칸 (Lv.1) (0) | 2025.02.27 |
---|---|
프로그래머스 | Python | 그리디 | 체육복 (Lv.1) (0) | 2025.02.27 |
프로그래머스 | Python | stack, 자료구조 | 크레인 인형뽑기 게임 (Lv.1) (0) | 2025.02.26 |
프로그래머스 | Python | 단순구현 | 숫자 짝궁 (Lv.1) (0) | 2025.02.26 |
프로그래머스 | Python | 단순구현 | [PCCE 기출문제] 10번 / 데이터 분석 (Lv.1) (0) | 2025.02.26 |