프로그래머스 햄버거 만들기 JAVA 풀이 (스택, 구현)

🔗 문제 링크

프로그래머스

---

📌 문제 개요

햄버거 재료가 순서대로 전달된다.

재료는 아래에서부터 차곡차곡 쌓이며 빵(1) → 야채(2) → 고기(3) → 빵(1) 순서가 완성되면 햄버거 하나를 포장한다.

 

포장된 재료는 즉시 제거되며, 남아있는 재료들로 다시 햄버거가 만들어질 수도 있다.

최종적으로 포장한 햄버거의 개수를 반환하는 문제이다.

---

📌 접근 방법

재료를 순서대로 확인하면서 스택에 저장한다.

새로운 재료가 들어올 때마다 스택의 마지막 4개의 재료가 1, 2, 3, 1인지 확인한다.

햄버거가 완성되었다면 마지막 4개의 재료를 제거하고 햄버거 개수를 증가시킨다.

 

입력 크기가 최대 100만이므로 ArrayList.remove()처럼 삭제 비용이 큰 자료구조보다는

배열을 스택처럼 사용하는 방식이 효율적이다.

---

📌 핵심 아이디어

1. 배열을 스택처럼 사용

재료를 순서대로 저장한다.

idx는 현재 스택의 크기를 의미한다.

stack[idx++] = ingredient[i];

---

2. 마지막 4개의 재료만 확인

햄버거는 마지막에 만들어질 수 있으므로

새로운 재료가 들어올 때마다 마지막 4개만 확인하면 된다.

if (idx >= 4 &&
    stack[idx - 4] == 1 &&
    stack[idx - 3] == 2 &&
    stack[idx - 2] == 3 &&
    stack[idx - 1] == 1)

---

3. 햄버거 제거

배열에서 실제 삭제하지 않고,

스택 크기만 줄이면 제거한 것과 같은 효과를 얻는다.

시간 복잡도는 O(1)이다.

idx -= 4;
answer++;

---

📌 전체 코드

class Solution {
    public int solution(int[] ingredient) {
        int answer = 0;

        int[] stack = new int[ingredient.length];
        int idx = 0;

        for (int food : ingredient) {
            stack[idx++] = food;

            if (idx >= 4 &&
                stack[idx - 4] == 1 &&
                stack[idx - 3] == 2 &&
                stack[idx - 2] == 3 &&
                stack[idx - 1] == 1) {

                idx -= 4;
                answer++;
            }
        }

        return answer;
    }
}

 

---

📄 정리

• 재료를 순서대로 스택에 저장한다.
• 마지막 4개의 재료만 확인하면 된다.
• 햄버거가 완성되면 스택 크기를 4 줄여 제거 효과를 낸다.
• 배열을 스택처럼 사용하면 최대 입력 크기에서도 효율적으로 해결할 수 있다.