문제
문제 : https://school.programmers.co.kr/learn/courses/30/lessons/133502
상수는 햄버거 가게에서 햄버거를 포장하는 일을 한다. 다른 직원이 햄버거 재료를 조리해 주면 조리된 순서대로 상수 앞에 아래에서부터 위로 쌓이고, 상수는 순서에 맞게 쌓여서 완성된 햄버거를 옮겨 포장한다. 상수네 햄버거 가게는 빵 - 야채 - 고기 - 빵 순서로 쌓인 햄버거만 포장하고, 상수가 포장하는 동안은 재료가 추가로 들어오지도 않는다. 재료가 쌓인 높이도 무시한다.
예로 들어, 상수 앞에 쌓인 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵] 일 때, 상수는 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때, 두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장한다.
상수에게 전해지는 재료의 정보를 나타내는 정수 배열 ingredient가 주어졌을 때, 상수가 포장하는 햄버거의 개수를 return 한다.
풀이
이 문제는 구현이 어렵다기 보다는, 문제를 제대로 이해하지 못해서 조금 애먹었다. 이 문제를 풀려면 다음과 같은 부분에 주목해야 한다.
- 재료는 아래에서부터 위로 쌓인다.
- 순서에 맞게 쌓여서 완성된 햄버거만 포장한다.
- 포장하는 동안 재료는 들어오지 않는다.
- 재료의 높이는 무시한다.
- 재료가 쌓이다가 햄버거 재료 순서에 맞으면 포장한다.
=> 나중에 쌓인 재료가 먼저 포장된다. 즉, 이 문제는 Stack을 사용하라는 문제다!
……이 부분만 알아차렸다면 문제 자체는 쉽게 풀 수 있다.
구현
1. 재료가 들어온 순서대로 stack에 쌓는다.
def solution(ingredient):
stack = []
answer = 0
for i in ingredient:
stack.append(i)2. 재료가 stack에 쌓일 때마다 마지막 4개 재료가 햄버거 재료 순서와 동일한지 확인한다.
동일하면 햄버거 개수 answer 값을 갱신하고, 마지막 4개 재료를 stack에서 없앤다.
def solution(ingredient):
stack = []
answer = 0
for i in ingredient:
stack.append(i)
if stack[-4:] == [1, 2, 3, 1]:
answer += 1
for t in range(4):
stack.pop()
return answer
참고로 아래처럼 슬라이싱을 해보기도 했는데, 이 방법은 시간 초과가 발생했다.
def solution(ingredient):
stack = []
answer = 0
for i in ingredient:
stack.append(i)
if stack[-4:] == [1, 2, 3, 1]:
answer += 1
stack = stack[:-4]
return answer
참고 문서
https://school.programmers.co.kr/learn/courses/30/lessons/133502