99클럽 코테 스터디_4기 33일차 TIL

TODAY TIL

문제 소개

햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 작업을 합니다. 재료들이 정해진 순서로 쌓이면 상수는 이를 포장합니다.
햄버거를 완성할 수 있는 순서는 아래와 같습니다:

• [빵(1) – 야채(2) – 고기(3) – 빵(1)]

주어진 재료 배열에서 햄버거를 몇 개 포장할 수 있는지 구하는 프로그램을 작성해봅시다.

---

문제 예시

입력:

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

출력:

2

설명:

1. 첫 번째 햄버거는 [1, 2, 3, 1]로 완성됩니다.
2. 두 번째 햄버거는 [1, 2, 3, 1]로 완성됩니다.
   결과적으로 2개의 햄버거를 포장할 수 있습니다.

---

문제 해결 접근법

1. 스택(Stack) 활용:
   • 스택을 사용하여 재료를 추가하면서 햄버거 완성 여부를 확인합니다.
   • 햄버거가 완성되면 스택에서 해당 재료들을 제거합니다.
2. 햄버거 완성 조건:
   • 스택의 마지막 4개의 재료가 [1, 2, 3, 1]인지 확인합니다.
3. 시간 최적화:
   • 슬라이싱 대신 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

 

실행 과정:

1. 스택에 [2] 추가 → 햄버거 완성 불가능.
2. 스택에 [2, 1] 추가 → 햄버거 완성 불가능.
3. 스택에 [2, 1, 1] 추가 → 햄버거 완성 불가능.
4. 스택에 [2, 1, 1, 2, 3, 1] 추가 → 햄버거 완성! 스택에서 제거 → [2, 1].
5. 나머지 재료를 처리하여 두 번째 햄버거 완성.

결과적으로 햄버거 2개 포장.

---

시간 및 공간 복잡도

1. 시간 복잡도:
   • 각 재료에 대해 stack.append()와 비교, 제거 연산이 이루어지므로 O(n).
2. 공간 복잡도:
   • 스택의 최대 크기는 ingredient와 동일하므로 O(n).

---

주요 개선 사항

• 슬라이싱 제거:
  기존의 stack[-4:] 대신, stack[-1], stack[-2], stack[-3], stack[-4]로 개별 접근하여 연산 속도 최적화.
• 불필요한 복사 연산 최소화:
  stack.pop()을 사용해 스택의 크기를 조정하며, 필요 없는 메모리 복사를 방지.

---

결론

이 문제는 스택 자료구조를 활용하여 재료의 순서를 관리하고, 햄버거 포장이 완료될 때마다 이를 제거하는 방식으로 효율적으로 해결할 수 있습니다. 최적화된 코드로 시간 초과 문제를 해결했으며, 스택 활용의 기본 개념을 연습하기에도 좋은 문제입니다.