프로그래머스 - 햄버거 만들기 자바

문제

풀이

정답

    public int solution(int[] ingredient) {
        int answer = 0;
        
        Stack<Integer> stack = new Stack<Integer>();
        
        int now = 0;
        for(int i = 0; i < ingredient.length; i++){
            now = ingredient[i];
            stack.push(now);
            
            if(stack.size() >= 4){
                if(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;
    }

오답

    public int solution(int[] ingredient) {
        int answer = 0;
        boolean[] visited = new boolean[ingredient.length];
        List<Integer> arr = new ArrayList<>();
        for(int i = 0; i < ingredient.length; i++){
            arr.add(ingredient[i]);
        }
        // boolean chk = true;
        int[] pos = new int[4];
        int idx = 0;
        String pre = "0";
        while(idx<arr.size()){
            if(visited[idx]){
                idx++;
                continue;
            }
            int now = arr.get(idx);
            if(now == 1){
                if(pre.equals("123")){
                    pos[3] = idx;
                    answer++;
                    pre = "0";
                    visited[pos[0]] = true;
                    visited[pos[1]] = true;
                    visited[pos[2]] = true;
                    visited[pos[3]] = true;
                }else{
                    pre = "1";
                    pos[0] = idx;
                }
            }else if(now == 2){
                if(pre.equals("1")){
                    pre+="2";
                    pos[1] = idx;
                }else{
                    pre = "0";
                }
            }else if(now == 3){
                if(pre.equals("12")){
                    pre+="3";
                    pos[2] = idx;
                }else{
                    pre = "0";
                }
            }
            idx++;
        }
        return answer;
    }

리뷰

풀이를 하면서도 ingredient의 길이 때문에 연산이 너무 많아지는게 아닌가 하는 생각이 들었다.
while문을 사용해서 리스트를 점검하고 있어 몇번이고 반복을 진행하게 되기 때문이다.
ArrayList를 이용해 1231이라는 문자가 완성되었을 경우 각 인덱스의 데이터를 지우는 방식으로 탐색 범위를 줄이려고 했으나, remove를 진행할 경우 인덱스가 바뀌는 문제로 인해 boolean배열을 이용해 각 인덱스가 방문을 했던 인덱스인지 체크를 하는 방식으로 변경하였다.
결과적으로 탐색하는 범위는 줄어들지 않고, 몇번이고 반복을 계속하게 되어 몇가지 테스트 케이스에서 시간 초과가 발생하였다.

반면 정답의 풀이에서처럼 스택을 이용한 풀이를 할 경우에 한번의 반복문만 진행한다.
스택의 특성을 이용해 스택에 저장되어 있는 맨 위의 데이터가 1,2,3,1일 경우에 pop을 수행하면 한번의 반복만을 이용해 정답을 도출할 수 있다.