TODAY TIL
문제 소개
햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 작업을 합니다. 재료들이 정해진 순서로 쌓이면 상수는 이를 포장합니다.
햄버거를 완성할 수 있는 순서는 아래와 같습니다:
- [빵(1) – 야채(2) – 고기(3) – 빵(1)]
주어진 재료 배열에서 햄버거를 몇 개 포장할 수 있는지 구하는 프로그램을 작성해봅시다.
문제 예시
입력:
ingredient = [2, 1, 1, 2, 3, 1, 2, 3, 1]
출력:
2
설명:
- 첫 번째 햄버거는 [1, 2, 3, 1]로 완성됩니다.
- 두 번째 햄버거는 [1, 2, 3, 1]로 완성됩니다.
결과적으로 2개의 햄버거를 포장할 수 있습니다.
문제 해결 접근법
- 스택(Stack) 활용:
- 스택을 사용하여 재료를 추가하면서 햄버거 완성 여부를 확인합니다.
- 햄버거가 완성되면 스택에서 해당 재료들을 제거합니다.
- 햄버거 완성 조건:
- 스택의 마지막 4개의 재료가 [1, 2, 3, 1]인지 확인합니다.
- 시간 최적화:
- 슬라이싱 대신 stack.pop()을 사용하여 불필요한 연산을 줄입니다.
최적화된 코드
아래 코드는 시간 초과를 방지하기 위해 최적화된 방식으로 작성되었습니다.
def solution(ingredient):
stack = [] # 재료를 담을 스택
count = 0 # 포장한 햄버거 개수
for item in ingredient:
stack.append(item) # 스택에 재료 추가
# 스택의 길이가 4 이상일 때 마지막 4개 요소를 직접 비교
if len(stack) >= 4:
if stack[-1] == 1 and stack[-2] == 3 and stack[-3] == 2 and stack[-4] == 1:
# 햄버거 완성 -> 스택에서 제거
stack.pop() # 빵 제거
stack.pop() # 고기 제거
stack.pop() # 야채 제거
stack.pop() # 빵 제거
count += 1 # 햄버거 개수 증가
return count
코드 실행 과정
입력:
ingredient = [2, 1, 1, 2, 3, 1, 2, 3, 1]
print(solution(ingredient)) # 출력: 2
실행 과정:
- 스택에 [2] 추가 → 햄버거 완성 불가능.
- 스택에 [2, 1] 추가 → 햄버거 완성 불가능.
- 스택에 [2, 1, 1] 추가 → 햄버거 완성 불가능.
- 스택에 [2, 1, 1, 2, 3, 1] 추가 → 햄버거 완성! 스택에서 제거 → [2, 1].
- 나머지 재료를 처리하여 두 번째 햄버거 완성.
결과적으로 햄버거 2개 포장.
시간 및 공간 복잡도
- 시간 복잡도:
- 각 재료에 대해 stack.append()와 비교, 제거 연산이 이루어지므로 O(n).
- 공간 복잡도:
- 스택의 최대 크기는 ingredient와 동일하므로 O(n).
주요 개선 사항
- 슬라이싱 제거:
기존의 stack[-4:] 대신, stack[-1], stack[-2], stack[-3], stack[-4]로 개별 접근하여 연산 속도 최적화. - 불필요한 복사 연산 최소화:
stack.pop()을 사용해 스택의 크기를 조정하며, 필요 없는 메모리 복사를 방지.
결론
이 문제는 스택 자료구조를 활용하여 재료의 순서를 관리하고, 햄버거 포장이 완료될 때마다 이를 제거하는 방식으로 효율적으로 해결할 수 있습니다. 최적화된 코드로 시간 초과 문제를 해결했으며, 스택 활용의 기본 개념을 연습하기에도 좋은 문제입니다.
'python' 카테고리의 다른 글
| 99클럽 코테 스터디_4기 34일차 TIL (0) | 2024.12.01 |
|---|---|
| 99클럽 코테 스터디_4기 32일차 TIL (1) | 2024.11.30 |
| 99클럽 코테 스터디_4기 31일차 TIL (1) | 2024.11.28 |
| 99클럽 코테 스터디_4기 30일차 TIL (0) | 2024.11.27 |
| 99클럽 코테 스터디_4기 29일차 TIL (1) | 2024.11.26 |
