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

문제 설명

햄버거 가게에서 직원이 특정 순서로 쌓인 재료를 포장한다. 재료 순서는 다음과 같다.
아래에서부터 [빵(1), 야채(2), 고기(3), 빵(1)] 순서로 쌓여야 햄버거로 인정.

접근 방법

1. 문제 분석
   햄버거 패턴 [1, 2, 3, 1]을 찾고 제거하는 작업을 반복 => 스택을 활용

• 스택의 상위 4개의 값만 확인하여 햄버거 패턴을 매칭한다.
• 패턴이 완성되면 스택에서 4개의 값을 제거해도 나머지 재료에 영향을 주지 않는다.

코드 구현

import java.util.Stack;

public class Solution {
    public int solution(int[] ingredient) {
        Stack<Integer> stack = new Stack<>();
        int count = 0; // 햄버거 개수

        for (int item : ingredient) {
            stack.push(item); // 재료를 스택에 추가

            // 스택 상단의 4개가 햄버거 패턴 [1, 2, 3, 1]인지 확인
            if (stack.size() >= 4) {
                int size = stack.size();
                if (stack.get(size - 4) == 1 &&
                    stack.get(size - 3) == 2 &&
                    stack.get(size - 2) == 3 &&
                    stack.get(size - 1) == 1) {
                    
                    // 패턴 발견 시, 스택에서 제거하고 햄버거 개수 증가
                    stack.pop();
                    stack.pop();
                    stack.pop();
                    stack.pop();
                    count++;
                }
            }
        }

        return count; // 포장된 햄버거 개수 반환
    }
}

더 생각해볼 점

1. 스택 대신 ArrayList를 활용하거나, 인덱스를 관리하여 불필요한 객체 생성을 줄일 수 있.
2. 만약 메모리 사용이 중요하다면 햄버거 패턴을 발견한 후 배열을 재구성하는 방식도 생각해 볼 필요가 있다.