[프로그래머스/Java] 햄버거 만들기

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/133502

프로그래머스

햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 일을 합니다. 함께 일을 하는 다른 직원들이 햄버거에 들어갈 재료를 조리해 주면 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓이게 되고, 상수는 순서에 맞게 쌓여서 완성된 햄버거를 따로 옮겨 포장을 하게 됩니다. 상수가 일하는 가게는 정해진 순서(아래서부터, 빵 – 야채 – 고기 - 빵)로 쌓인 햄버거만 포장을 합니다. 상수는 손이 굉장히 빠르기 때문에 상수가 포장하는 동안 속 재료가 추가적으로 들어오는 일은 없으며, 재료의 높이는 무시하여 재료가 높이 쌓여서 일이 힘들어지는 경우는 없습니다.

예를 들어, 상수의 앞에 쌓이는 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵] 일 때, 상수는 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때, 두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장합니다. 즉, 2개의 햄버거를 포장하게 됩니다.

상수에게 전해지는 재료의 정보를 나타내는 정수 배열 ingredient가 주어졌을 때, 상수가 포장하는 햄버거의 개수를 return 하도록 solution 함수를 완성하시오.

제한 사항

• 1 ≤ ingredient의 길이 ≤ 1,000,000
• ingredient의 원소는 1, 2, 3 중 하나의 값이며, 순서대로 빵, 야채, 고기를 의미합니다.

입출력 예

ingredient	result
[2, 1, 1, 2, 3, 1, 2, 3, 1]	2
[1, 3, 2, 1, 2, 1, 3, 1, 2]	0

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 상수가 포장할 수 있는 햄버거가 없습니다.

 

내가 작성한 코드

import java.util.*;

class Solution {
    public int solution(int[] ingredient) {
        // 만들 수 있는 햄버거의 개수
        int answer = 0;
        
        // 햄버거 재료 저장할 스택 생성
        Deque<Integer> stack = new ArrayDeque<>();
        
        // 햄버거 재료 순회하면서 햄버거 만들기
        for (int ing : ingredient) {
            // 스택에 햄버거 재료 저장
            stack.push(ing);
            
            // 스택의 크기가 4 이상일 경우 재료 확인
            if (stack.size() >= 4) {
                // 순서대로 재료 저장
                int a = stack.pop();
                int b = stack.pop();
                int c = stack.pop();
                int d = stack.pop();
                
                // 햄버거 패턴과 비교하여 맞을 경우 햄버거 개수 +1
                if (d == 1 && c == 2 && b == 3 && a == 1) {
                    answer++;
                // 아닐 경우 재료 되돌리기
                } else {
                    stack.push(d);
                    stack.push(c);
                    stack.push(b);
                    stack.push(a);
                }
            }
        }
        
        // 만든 햄버거 개수 반환
        return answer;
    }
}

문제를 풀기 위해 생각한 방향

처음 문제를 봤을 때, 핵심은 재료 배열을 처음부터 끝까지 훑으면서 최근에 쌓인 네 개가 1-2-3-1인지만 지속적으로 확인하면 된다고 보였 다. 중간 어딘가에서 패턴이 완성되면 그 4개를 제거하고 카운트를 올리면 되고, 이후 검사도 “이전 상태에서 이어서” 하면 겹치는 패턴까지 자연스럽게 잡힌다고 판단했다.

조건을 분석해 보니, 매번 리스트 앞쪽부터 다시 확인하거나 중간 원소를 삭제하면 비용이 커진다. 특히 ArrayList로 중간 제거를 반복하면 연속적인 이동 비용 때문에 최악의 경우 O(n²)까지 갈 수 있다고 보였 다. 또 큐처럼 앞에서 빼고 뒤에서 넣는 구조는 “최근 4개”를 직관적으로 다루기 어렵다.

그래서 자료구조는 Deque를 스택처럼 쓰는 게 최적이라고 결정했다. 스택은 항상 맨 위(가장 최신)만 보면 되기 때문에 “최근 4개” 검사에 딱 맞고, push/pop이 O(1)로 가볍다. 또한 Deque는 인덱스 접근(get)이 없어 실수 가능성이 적고, peek만으로는 4개 동시 확인이 어려우니 필요시 4개를 꺼내서 확인한 뒤 맞으면 버리고, 아니면 복원하는 방식이 자연스럽다.

로직 흐름은 이렇다. 재료를 하나씩 push 하여 쌓는다. 스택 크기가 4 이상이 되는 순간마다 맨 위에서 4개를 pop 해 임시 버퍼(길이 4짜리 고정 배열 등)에 담는다. pop의 특성상 꺼낸 순서는 위→아래이므로, 비교 시 역순 정합성을 유의해 1-2-3-1 패턴과 일치하는지 확인한다. 일치하면 이미 4개가 제거된 상태이므로 복원 없이 카운트만 증가한다. 불일치하면 방금 꺼낸 4개를 원래 순서로 복원하기 위해 꺼낸 역순으로 다시 push 한다. 이 과정을 끝까지 반복하면, 서로 겹치는 패턴도 자동으로 처리된다.

주의할 점은 세 가지다. 첫째, Deque에는 인덱스 기반 get이 없으니 인덱스로 비교하려 들지 않는다. 둘째, peek만으로는 4개를 동시에 안전하게 확인하기 어렵다. 셋째, 임시 버퍼는 고정 크기 배열을 재사용하면 매 반복마다 리스트/배열을 새로 만들지 않아 효율성 테스트에 유리하다. 배열 비교는 참조 동등성(==)이 아니라 내용 비교를 해야 한다는 점도 잊지 않는다.

시간복잡도는 입력 길이를 n이라 할 때, 각 원소를 한 번씩 push 하고, 검사 시 최대 4번의 pop/push만 수행하므로 전체가 O(n)이다. 추가 메모리는 스택과 길이 4의 임시 버퍼 정도로 O(n)/O(1) 수준이며, ArrayList 기반의 반복 삭제·재검사보다 훨씬 안정적으로 효율성 조건을 통과할 수 있다고 판단했다.