[프로그래머스/ 코딩테스트 연습문제] 햄버거 만들기

Q. 햄버거 만들기

A1. Title: 햄버거 만들기, Time: 100.33 ms, Memory: 95.9 MB

import java.util.Stack;

class Solution {
    public int solution(int[] ingredient) {
        // answer : 완성된 햄버거 개수
        int answer = 0;
        
        // 재료를 쌓을 stack 
        // stack -> LIFO(Last In First Out) 후입선출 방식
        Stack<Integer> stack = new Stack<>();
        
        // ingredient 배열의 각 재료를 순서대로 처리
        // 현재 재료를 push해서 stack에 쌓기
        for(int i : ingredient){
            stack.push(i);
            
            // 햄버거는 4개의 재료로 만들어지니까 스택에 재료가 4개 이상 쌓여 있을 때 순서 확인
            if(stack.size() >= 4){
                int size = stack.size();
                
                // 스택의 마지막 4개 재료가 1,2,3,1 순서인지 확인
                if(stack.get(size - 4) == 1 &&
                  stack.get(size - 3) == 2 &&
                  stack.get(size - 2) == 3 &&
                  stack.get(size - 1) == 1){
                    
                    // 올바른 순서일 경우 햄버거가 완성된 것이므로, 마지막 4개 재료 제거
                    stack.pop();
                    stack.pop();
                    stack.pop();
                    stack.pop();
                    
                    // 완성된 햄버거 개수 +1 증가
                    answer++;
                }
            }
        }
        return answer;
    }
}

• 배열은 메모리에 연속적으로 저장된 데이터에 빠르게 접근할 수 있는 반면, 스택은 요소에 접근하기 위해 요소들을 하나씩 순회해야 하므로 속도가 느림 

A2. Title: 햄버거 만들기, Time: 16.05 ms, Memory: 125 MB

class Solution {
    public int solution(int[] ingredient) {
        int answer = 0;
        
        // stack과 비슷한 역할을 할 배열 생성
        // -> ingredient와 같은 크기로 생성
        int[] stack = new int[ingredient.length];
        // 빈 배열에서 시작해야하니까 -1로 초기화 (배열은 0부터 시작)
        int top = -1;
        
        for(int i : ingredient){
            // ++top을 해서 배열 위치를 지정 후 재료를 그 위치에 저장
            // -> push와 같은 역할
            stack[++top] = i;
            
            // 최소 4개의 재료가 있어야하니까 [0,1,2,3] top이 3이상일 경우 순서 확인
            if(top >= 3){
                if(stack[top - 3] == 1 &&
                  stack[top - 2] == 2 &&
                  stack[top - 1] == 3 &&
                  stack[top] == 1){
                    
                    // 올바른 순서일 경우 재료 4개 배열에서 제거
                    top -= 4;
                    
                    answer++;
                }
            }
        }
        return answer;
    }
}