[프로그래머스] 햄버거 만들기 / 자바(Java)

문제

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

프로그래머스

 

---

해설

아래에서부터 쌓이는 재료들이 특정 순서(빵, 야채, 고기, 빵  / 1,2,3,1) 일 때만 포장해 최종적으로 나오는 햄버거의 개수를 구하는 문제입니다.

 

입출력 예에 따라

[2, 1, 1, 2, 3, 1, 2, 3, 1] 이 차례로 들어올 때 

1. 처음 6번째 까지 재료가 들어왔을 때 [2,1,1,2,3,1] 에서 1개가 만들어지고 남은 재료는 [2,1]이 됩니다.

2. 이후 들어오는 모든 재료를 받으면 [2,1,2,3,1]이 되어 다시 1개 만들어지고 재료는 [2]만 남고 추가 재료가 없이 종료되어 최종적으로 2개의 햄버거가 완성됩니다.

 

문자열에서 부분 문자열을 찾는 String의 indexOf를 사용하는 경우 부분 문자열을 삭제하고 새로 만드는 과정과 다시 처음부터 탐색하는 indexOf의 내부 구조상 탐색할 배열의 길이가 길어 시간 초과가 나기 쉽습니다.

 

아래부터 쌓인다는 키워드로 Stack 자료구조를 사용하는것이 효율적이라 생각해 배열의 요소를 Stack s에 몰아두며 s의 크기가 4개 이상(햄버거가 만들어질 수 있는 최소 조건)인 경우일 때만 가장 위의 4개의 재료를 확인해 포장 여부를 파악하는 구조로 만들었습니다. 입력 배열만큼의 for문이 구성되어 O(n)의 시간복잡도로 구현가능합니다.

주의점

• 배열 ingredient의 길이가 1,000,000로 시간 및 공간 복잡도를 고려해야 한다

---

코드

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

 

추가 풀이

다른 분들의 풀이를 보다 발견한 재미있는 풀이법 입니다.

 

자바에서 제공하는 Stack을 사용하지 않고 배열의 index를 이용해 Stack처럼 표현합니다.

기본적인 방식은 같으나 Stack의 pop을 index를 뒤로 돌리는 것으로 변경하였습니다.

이때 배열의 값을 초기화해주지 않아도 배열의 조회는 인덱스값 이전의 4개만 하기 때문에 오류없이 결과가 나옵니다.

 

우선 Stack자료구조를 만들지 않고 또 조회가 더 빠른 배열을 사용하여 더 빠르고 용량을 적게 차지하는 풀이법이 된다고 생각합니다.

Stack관련 문제를 풀 때 한번 쯤 기억해 두면 좋을 듯 합니다.

 

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