프로그래머스 Level1 햄버거 만들기 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/133502?language=java

문제설명

• 햄버거를 완성해 포장해야 한다.
• 재료가 주어지는데 순서는 항상 정해져 있다. (빵 – 야채 – 고기 - 빵)
• 햄버거가 완성되면 이전에 쌓였던 재료를 가지고 햄버거를 만들 수 있다.

제한사항

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

코드

import java.util.Stack;

public class Solution {
    public int solution(int[] ingredient) {
        int answer = 0;
        Stack<Integer> stack = new Stack<>();
        int[] burger = {1,2,3,1};
        for(int i = 0; i < ingredient.length; i++) {
            stack.add(ingredient[i]);
            int curIndex = stack.size()-1;
            int burgerIndex = 3;
            if(stack.size() >= 4) {
                for(int j = curIndex; j > curIndex-4; j--) {
                    if(burger[burgerIndex--] == stack.elementAt(j)) {
                        if(j == curIndex-3) {
                            answer+=1;
                            for(int k = 0; k < 4; k++) {
                                stack.pop();
                            }
                        }
                    }else {
                        break;
                    }
                }
            }
        }
        return answer;
    }
}

풀이

• ingredient의 길이가 백만이므로 O(n)으로 해결해야 한다.
• 이전의 재료를 활용할 수 있기 때문에 stack을 이용해 완성되면 pop을 해서 이전의 재료들을 활용한다.