[프로그래머스][JAVA] 택배상자

🤔 시간 초과

기존 컨베이너 벨트도 그렇고 보조 컨베이너 벨트도 그렇고 스택이나 큐를 사용하면 쉽게 풀 수 있을 것 같았고, 둘 다 스택과 큐를 만들어서 해결해보려고 했다. 최대 길이가 100만개고 order길이만큼만 반복문이 돌아가니까 시간복잡도 측면에서 그래도 괜찮지 않을까라는 생각으로 문제를 풀이했는데 논리는 맞았으나 시간 초과가 났다..

import java.util.*;
class Solution {
    public int solution(int[] order) {
        int answer = 0;
        List<Integer> basis = new ArrayList<>();
        Stack<Integer> assist = new Stack<>();
        for(int i = 1 ; i <= order.length; i++)
            basis.add(i);
        
        //order순회
        for(int curFind = 0; curFind < order.length; curFind++){
            //종료해야할 거 같다면(기존 컨테보다 작은데 && 보조 컨베 젤 위보다 작아)
            if(!basis.isEmpty() && !assist.isEmpty() && basis.get(0) > order[curFind] && assist.peek() > order[curFind])
                break;
            
            //보조 컨베에서 꺼낼 수 있다(스택 최상단 == 찾는 거)
            if(!assist.isEmpty() && assist.peek() == order[curFind]){
                assist.pop();
                answer++;
                continue;
            }
            
            //기존 컨베에 있긴한데 계속 꺼내야 하는 상황
            if(!basis.isEmpty() && order[curFind] >= basis.get(0)){
                //기존 컨베에서 원하는게 나올 때까지 보조 컨베에 옮기는 작업!
                while(basis.get(0) < order[curFind]){
                    //기존 컨베 제거 && 보조 컨베에 넣기
                    assist.add(basis.remove(0));
                }
                //-1 까지 옮기고
                //해당 위치 제거
                basis.remove(0);
                answer++;
            }
        }
        
        
        return answer;
    }
}

🙄 원인

아마 스택과 큐를 제거하고 삽입하는 과정에서 내가 생각하는 것보다도 훨씬 더 많은 시간이 소요되는 듯하다.

#스택

• 삽입,삭제, top읽기 : o(1)

#연결리스트

• add : o(1)
• 제거 : o(n)
• get : o(1)
• 검색 : o(n)

지금 이렇게 정리를 하며 느낀 것은 내가 큐를 사용하지 않고 그냥 연결리스트를 사용했는데 그걸 그냥 큐처럼 사용한 것이다..일단 큐로 바꿔서 다시 시도!!!

맞았다!! 블로그를 정리하면서 깨달았던 부분을 고치니 바로 해결!

---

💻 성공 코드

import java.util.*;
class Solution {
    public int solution(int[] order) {
        int answer = 0;
        Queue<Integer> basis = new LinkedList<>();
        Stack<Integer> assist = new Stack<>();
        for(int i = 1 ; i <= order.length; i++)
            basis.add(i);
        
        //order순회
        for(int curFind = 0; curFind < order.length; curFind++){
            //종료해야할 거 같다면(기존 컨테보다 작은데 && 보조 컨베 젤 위보다 작아)
            if(!basis.isEmpty() && !assist.isEmpty() && basis.peek() > order[curFind] && assist.peek() > order[curFind])
                break;
            
            //보조 컨베에서 꺼낼 수 있다(스택 최상단 == 찾는 거)
            if(!assist.isEmpty() && assist.peek() == order[curFind]){
                assist.pop();
                answer++;
                continue;
            }
            
            //기존 컨베에 있긴한데 계속 꺼내야 하는 상황
            if(!basis.isEmpty() && order[curFind] >= basis.peek()){
                //기존 컨베에서 원하는게 나올 때까지 보조 컨베에 옮기는 작업!
                while(basis.peek() < order[curFind]){
                    //기존 컨베 제거 && 보조 컨베에 넣기
                    assist.add(basis.remove());
                }
                //-1 까지 옮기고
                //해당 위치 제거
                basis.remove();
                answer++;
            }
        }
        
        
        return answer;
    }
}