[프로그래머스] LV.1 햄버거 만들기 - Java [69/80]

💬 문제 설명

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

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

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

 

🚫 제한 사항

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

 

📢 입출력 예

 

👨‍🏫 입출력 예 설명

 

📃 제출 코드

import java.util.Stack;
class Solution {
    public int solution(int[] ingredient) {
        Stack<Integer> stack = new Stack<>();
        
        int answer = 0;
        for (int n : ingredient) {
            
            stack.add(n);
            
            if (stack.size() >= 4 
                && stack.get(stack.size() - 4) == 1 
                && stack.get(stack.size() - 3) == 2
                && stack.get(stack.size() - 2) == 3
                && stack.get(stack.size() - 1) == 1
               ){
                answer++;
                stack.pop();stack.pop();stack.pop();stack.pop();
            }
        }

        return answer;
    }
}

실패코드 - LinkedList 사용

import java.util.LinkedList;

class Solution {
    public int solution(int[] ingredient) {
        int[] recipe = {1,2,3,1};
        LinkedList<Integer> list = new LinkedList<>();
        for (int i : ingredient) {
            list.add(i);
        }

        int answer = 0;
        int order = 0;
        
        for (int i = 0; i < list.size();) {
            if (list.get(i) == recipe[order]) {
                order++;
                if (order == recipe.length) {
                    for (int j = 0; j < recipe.length; j++) {
                        list.remove(i - j);
                    }
                    answer++;
                    order = 0;
                    i = 0;
                }else {
                    i++;
                }
            }else {
                order = list.get(i) == recipe[0] ? 1 : 0;
                i++;
            }
        }
        
        return answer;
    }
}

✏문제 접근방법  & 해결방법

첫 번째 시도에서는 LinkedList를 사용하여 문제를 해결해 보았습니다. 재료의 순서를 담은 배열을 정의하고, 햄버거 재료를 LinkedList에 저장한 후, 재료의 순서와 비교하여 햄버거를 만들 수 있는 경우 리스트의 요소를 삭제하고 다시 순회하도록 했으나, 이 방법은 시간 초과가 발생했습니다.

 

두 번째 시도에서는 Stack을 사용하여 문제를 해결해 보았습니다. 문제를 처음 접했을 때 Stack이 가장 먼저 떠올랐으나, LinkedList를 활용해 시도해 보았지만 실패했습니다. 스택을 활용하여 햄버거의 재료를 순차적으로 저장하면서, 스택의 상단에서 햄버거 재료의 순서가 1, 2, 3, 1인지 확인하고, 만약 일치할 경우 해당 재료를 제거하고 햄버거 카운트를 증가시키는 방식으로 문제를 해결하였습니다.

📚 얻어가기

LinkedList와 ArrayList의 성능 차이를 다음과 같이 배웠습니다

• LinkedList의 특징
  • 요소를 삽입하거나 삭제할 때는 O(1)의 성능을 가집니다.
    • 이는 노드 간의 참조를 단순히 변경하면 되기 때문입니다.
  • 특정 인덱스에 접근할 때는 O(n)의 시간이 걸립니다.
    • 배열과 달리, 노드를 순차적으로 접근해야 하므로 직접적인 인덱스 접근이 불가능합니다.
• ArrayList의 특징
  • 특정 인덱스에 접근하는 데는 O(1)의 시간이 걸립니다.
    • 배열 기반 데이터 구조로, 인덱스를 통해 직접 접근할 수 있기 때문입니다.
  • 중간에서의 삽입이나 삭제는 요소를 이동시켜야 하므로 O(n)의 시간이 소요됩니다.
    • 즉, 배열의 크기 조정과 요소 이동이 필요합니다.

따라서, 요소에 접근하는 경우가 많을 경우에는 ArrayList를 사용하는 것이 효율적이며, 중간에서의 삽입이나 삭제가 빈번한 경우에는 LinkedList를 사용하는 것이 적합하는것을 직접 코드로 작성해보며 성능을 확인해보았습니다.