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

📌 문제

프로그래머스

📌 풀이

스택으로 쉽게 풀 수 있었던 문제지만 stack.get()으로도 스택에 있는 값을 확인할 수 있다는 걸 몰라서 헤맸다(...)

풀이 과정을 간단하게 설명하면 다음과 같다.

• 스택을 선언한다.
• ingredient 배열을 돌면서 요소를 스택에 저장한다.
  • 스택의 길이가 4 이상이 될 경우
    • 스택의 마지막 요소가 1이고, 그 다음 요소가 3, 그다음 요소가 2, 마지막에서 4번째 요소가 1일 경우, 빵 - 야채 - 고기 - 빵 순서이므로 4개를 모두 꺼낸다.
    • 햄버거의 개수 answer를 1 증가시킨다.

for (int i : ingredient) {
    stack.push(i);
    if (stack.size() >= 4) {
        if (stack.get(stack.size() - 1) == 1
           && stack.get(stack.size() - 2) == 3
           && stack.get(stack.size() - 3) == 2
           && stack.get(stack.size() - 4) == 1) {
            stack.pop();
            stack.pop();
            stack.pop();
            stack.pop();
            answer++;
        }
    }
}

📌 다른 풀이 - 배열로 풀기

다른 사람들의 풀이를 보니 스택을 사용하지 않고 배열만을 이용해서 풀 수 있었다. 햄버거가 완성되면 그 요소들을 삭제시키는 것만 생각했는데, 삭제하지 않고 그 위로 덮어 씌워도 삭제한 것처럼 동작시킬 수 있었다.

 

먼저 ingredient 배열의 길이를 가진 stack 배열을 선언한다. stack 배열 인덱스로 사용할 idx 변수도 만든다.

int answer = 0;
int[] stack = new int[ingredient.length];
int idx = 0;

 

그리고나서 ingredient 배열을 돌면서 stack 배열에 요소를 넣는다. 동시에 idx를 증가시킨다. 계속 요소를 넣으면서 idx가 4 이상이면서 특정한 자리의 요소들이 빵 - 야채 - 고기 - 빵 순일때, 햄버거 개수 answer를 1 증가시키고 idx에서 4를 뺀다. 4를 빼면 마치 해당 요소를 삭제한 것처럼 그 위에 덮어쓸 수 있다.

for (int i : ingredient) {
    stack[idx++] = i;
    
    if (idx >= 4 && stack[idx - 1] == 1
       && stack[idx - 2] == 3
       && stack[idx - 3] == 2
       && stack[idx - 4] == 1) {
        idx -= 4;
        answer++;
    }
}

📌 전체 코드

스택으로 푸는 방법

import java.util.*;

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

배열로 푸는 방법

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