[Programmers] 햄버거 만들기 - Java

문제

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

프로그래머스

 

풀이

재료에 대한 번호가 주어졌을때, 햄버거에 대한 쌍으로 쌓여서 만들 수 있는 개수를 구하는 문제이다.

 

재료에 대해서 쌓는다고 적혀 있어서 바로 스택을 사용해야겠다는 생각을 했다.

 

빵이면서, 햄버거를 만들 수 있는 개수가 스택에 있다면

쌍을 모두 꺼내서 햄버거를 만들 수 있는지 확인해보면 된다.

 

첫번째 풀이

1. 스택을 선언한다.

 

2. 현재 스택에 저장되어 있는 재료의 개수가 4개 이상이고, 제일 상위에 있는 재료가 빵이라면

 

2-1. 4개의 재료를 모두 꺼내서 쌍이 되는지 확인하고, 쌍이 되지 않는다면 다시 넣는다.

 

2-2. 4개의 재료를 모두 꺼냈을 때, 햄버거를 만들 수 있다면, 개수를 센다.

 

두번째 풀이

배열 + 인덱스 연산으로 풀이

 

1. 재료를 담을 배열을 만든다.

 

2. 현재 배열에 저장되어 있는 재료의 개수가 4개 이상이고, 제일 상위에 있는 재료가 빵이라면

 

2-1. 4개의 재료를 인덱스로 접근해서 햄버거 쌍이 되는지 확인하고 햄버거를 만들 수 있다면 개수를 세고 인덱스를 4를 감소시킨다.

 

소스코드

import java.util.ArrayDeque;

class Solution {
    final int BREAD = 1;
    final int VEGETABLE = 2;
    final int MEAT = 3;
    final int PAIR_NUMBER = 4;
    
    public int solution(int[] ingredient) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        
        int answer = 0;
        
        for (int ingre : ingredient) {
            stack.addFirst(ingre);
            
            if (stack.size() >= PAIR_NUMBER && stack.peekFirst() == BREAD) {
                int fourth = stack.removeFirst();
                int third = stack.removeFirst();
                int second = stack.removeFirst();
                int first = stack.removeFirst();
                
                if (first != BREAD || second != VEGETABLE || third != MEAT || fourth != BREAD) {
                    stack.addFirst(first);
                    stack.addFirst(second);
                    stack.addFirst(third);
                    stack.addFirst(fourth);
                    continue;
                }
                
                answer++;
            }
            
        }

        return answer;
    }
}

class Solution {
    final int BREAD = 1;
    final int VEGETABLE = 2;
    final int MEAT = 3;
    final int PAIR_NUMBER = 4;
    
    public int solution(int[] ingredient) {
        int[] stack = new int[ingredient.length];
        
        int answer = 0;
        int idx = 0;
        
        for (int ingre : ingredient) {
            stack[idx++] = ingre;
            
            if (idx >= PAIR_NUMBER && stack[idx - 1] == BREAD && stack[idx - 2] == MEAT && stack[idx - 3] == VEGETABLE && stack[idx - 4] == BREAD) {
                idx -= PAIR_NUMBER;
                answer++;
            }
        }

        return answer;
    }
}

 

실행결과

스택 풀이

배열 풀이

 

성능개선

구분	평균 실행 시간(ms)	평균 메모리 사용량(MB)
스택 풀이	27.77	96.77
배열 풀이	5.52	94.78
개선	80.1% 향상	2.1% 감소