99클럽 코테 스터디 4일차 TIL 햄버거 만들기 문제(ArrayList remove vs Stack pop)

 

 

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

프로그래머스

 

문제를 해석하자면 결국 주어진 수 배열에서 1,2,3,1 의 배열이 있다면 제거하고 뒤의 숫자를 당긴다음

또 1,2,3,1의 배열이 있는지 확인하여 몇개가 있었는지 출력하는 문제이다.

배열을 arraylist로 변환 하는 생각이 먼저 떠올라

 

첫번째 코드를 작성하였다.

public int solution(int[] ingredient) {
        //빵 – 야채 – 고기 - 빵
        //1-2-3-1 일때
        ArrayList<Integer> ingredientList = new ArrayList<>();
        int answer = 0;
        for(int i : ingredient){
            ingredientList.add(i);
        }
        
        //[2, 1, 1, 2, 3, 1, 2, 3, 1]
        //
        for(int i = 0;i <= ingredientList.size() -4 ;){
            if(ingredientList.get(i) == 1 && ingredientList.get(i+1) == 2 && ingredientList.get(i+2) ==3
                    && ingredientList.get(i+3) ==1 ){
                
                answer++;
                ingredientList.remove(i);
                ingredientList.remove(i);
                ingredientList.remove(i);
                ingredientList.remove(i);
                i = 0;
            }
            else{
                i++;
            }
        }


        return answer;
    }

 

하지만 런타임 에러가 나오게 되었다.

 

코드를 이래저래 수정하다가 시간이 다 되어 결국 다른 스터디원의 발표를 보았는데

그 분은 스택을 사용하였었다. 코드의 알고리즘은 별 차이가 없어 내코드를 그 분의 코드를 보고 수정하여

 

2번째 코드 

public int solution(int[] ingredient) {
        //빵 – 야채 – 고기 - 빵
        //1-2-3-1 일때
        Stack<Integer> ingredientList = new Stack<>();
     
        
         //[2, 1, 1, 2, 3, 1, 2, 3, 1]
        int answer = 0;
        for(int i : ingredient){
            ingredientList.add(i);
            if(ingredientList.size() >= 4){ //4개 이상 쌓이면
                int index = ingredientList.size() -1;
                if(ingredientList.get(index -3) == 1 && ingredientList.get(index-2) == 2 
                   && ingredientList.get(index-1) ==3 && ingredientList.get(index) ==1){
                    ingredientList.pop();
                    ingredientList.pop();
                    ingredientList.pop();
                    ingredientList.pop();
                    answer++;
                    
                }
            }
            
            
        }
        
        

        return answer;
    }

 

와 같이 수정하였지만 그래도 런타임이 떴다.

그래서 설마하며 ingredientList를 스택으로 바꾸고 pop형식으로 바꾸었더니

 

최종 코드

public int solution(int[] ingredient) {
        //빵 – 야채 – 고기 - 빵
        //1-2-3-1 일때
        Stack<Integer> ingredientList = new Stack<>();
     
        
         //[2, 1, 1, 2, 3, 1, 2, 3, 1]
        int answer = 0;
         
        for(int i : ingredient){
            ingredientList.add(i);
            if(ingredientList.size() >= 4){ //4개 이상 쌓이면
                int index = ingredientList.size() -1;
                if(ingredientList.get(index -3) == 1 && ingredientList.get(index-2) == 2 
                   && ingredientList.get(index-1) ==3 && ingredientList.get(index) ==1){
                    ingredientList.pop();
                    ingredientList.pop();
                    ingredientList.pop();
                    ingredientList.pop();
                    answer++;
                    
                }
            }
            
            
        }
        
        

        return answer;
    }

 

그랬더니

통과 되었다. 

 

그래서 ArrayList와 Stack의 차이를 찾아가며 왜 안되었던것인지 생각 하였는데

ArrayList의 remove를 사용하면서 remove의 해당 값을 찾는 과정으로 인해 시간이 걸리게 되는 것같다.

stack은 바로 위의 것을 제거 하면 되지만 remove는 해당 값을 찾고 삭제를 하는 과정을 거치게 되는 것이다.