코테 풀이

TIL - 햄버거 가게 문제 해결 (스택 & 동적 메모리)

문제 요약

• 상수는 빵–야채–고기–빵(1 2 3 1) 순서로 쌓인 재료만 포장 가능하다.
• 재료는 순차적으로 상수 앞에 쌓이며, 올바른 패턴이 감지되면 해당 재료 4개를 제거하고 햄버거 1개를 포장한다.
• 재료 배열이 주어졌을 때, 총 몇 개의 햄버거를 포장할 수 있는지 구하는 문제.

---

사용한 개념

1. 스택 자료구조

• 재료는 쌓이는 구조이기 때문에 **후입선출(LIFO)**인 스택을 사용.
• 새로운 재료가 들어올 때마다 스택에 push하고, 가장 위에서부터 4개가 [1, 2, 3, 1]인지 검사함.

2. 동적 메모리 할당 (malloc)

• 입력 배열의 길이가 매번 달라질 수 있어, 스택을 고정 배열이 아닌 동적 배열로 구현.
• malloc을 사용하면 프로그램 실행 중 필요한 크기만큼 메모리를 할당할 수 있음.
• 스택처럼 사용할 배열을 동적으로 할당하고, 다 사용한 뒤에는 free()로 메모리 해제해야 함.

 

정답 코드

1. top >= 3:
   • 스택에 최소한 4개 이상의 재료가 쌓여야 햄버거 [1, 2, 3, 1]를 만들 수 있음.
   • 인덱스는 0부터 시작하니까, top이 3 이상이어야 4개를 비교할 수 있음.
2. stack[top - 3] == 1: 4번째 전 재료가 빵인지 확인
3. stack[top - 2] == 2: 3번째 전 재료가 야채인지 확인
4. stack[top - 1] == 3: 2번째 전 재료가 고기인지 확인
5. stack[top] == 1: 맨 위 재료가 빵인지 확인

→ 이 네 조건을 모두 만족하면, 스택 상단에 [1, 2, 3, 1] = 빵-야채-고기-빵 순으로 재료가 쌓여 있는 것입니다. 즉, 햄버거 하나 완성