[Java]프로그래머스 - 디스크 컨트롤러

코딩테스트 연습 - 디스크 컨트롤러

프로그래머스

 

문제풀이 & 전체 시간 복잡도

• 작업의 소요시간을 오름차순으로 유지하기 위해 PriorityQueue로 나타낸다.
  1. 현재 시간 보다 작거나 같은 요청 시간 큐에 추가
  2. 큐에 작업이 없다면 작업 요청 시점이 가장 빠른 작업 추가
  3. 큐에 작업이 있다면 작업 소요 시간이 가장 빠른 작업 수행
  전체 시간복잡도
• 1. 초기 정렬 (Arrays.sort): O(N log N)
  • 가장 먼저 수행되는 Arrays.sort(jobs, ...) 부분입니다.
  • N개의 작업이 담긴 배열을 요청 시점 순으로 정렬하므로 O(N log N)
• 2. 우선순위 큐 조작 (PriorityQueue): O(N log N)
  • while 루프 안에서 일어나는 일들입니다.
  • 모든 작업(N개)은 반드시 큐에 한 번 추가(offer)되고, 한 번 추출(poll)됩니다.
  • 힙(Heap) 구조인 우선순위 큐에서 추가와 추출은 각각 O(log N)이 걸립니다.
  • 따라서 총 N번의 작업을 처리하므로 이 과정 전체는 O(N log N)입니다.

• 3. 전체 루프 순회: O(N) while(!pq.isEmpty() || idx < len) 부분입니다.
  • idx 변수가 len까지 증가하고, pq에서 모든 요소를 꺼낼 때까지 반복됩니다.
  • 내부의 while(idx < len && ...) 문도 결국 전체적으로 보면 idx가 0부터 N까지 한 번 훑고 지나가는 것이므로, 큐 조작을 제외한 순수 루프 방문 횟수는 O(N)에 해당합니다.

• 최종 시간 복잡도: O(N log N)
  • 빅오 표기법은 가장 영향력이 큰 항을 따르므로, 이 알고리즘의 최종 시간 복잡도는 O(N log N)

    ---

    초기 정렬, 우선순위 큐는 왜 O Nlog N 일까?

 

코드

public int solution(int[][] jobs){
        int answer = 0;
        int time = 0;
        int idx = 0;
        int len = jobs.length;

        //작업의 소요시간 오름차순 정렬
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        //작업 요청시점 오름차순 정렬
        Arrays.sort(jobs, new Comparator<int[] >() {
                    @Override
                    public int compare(int[] o1, int[] o2) {
                        return o1[0] - o2[0];
                    }
        });

        while(!pq.isEmpty() || idx < len){
            //현재 시간 보다 작거나 같은 요청시점을 큐에 추가 한다.
            //즉 pq에는 "현재 시각에 도착한 작업들"만 들어간다.
            while(idx < len && jobs[idx][0] <= time){
                pq.offer(jobs[idx++]);
            }
            //1. 큐에 작업이 없다면
            // 작업 요청시점이 가장 빠른 작업 추가
            // = CPU가 할 일이 없는 상태 ex)time=3
            //다음 작업 요청시간 10이 들어오면 time을 10으로 이동
            if(pq.isEmpty()){             
                time = jobs[idx][0];
            }
            //2. 큐에 작업이 있다면
            //대기 큐에서 작업 소요시간이 가장 짧은 작업을 꺼내서 작업을 시킴
            //(작업 완료 시각 - 요청 시각)을 answer에 누적 한다.
            else{
                int[] job = pq.poll();
                time += job[1];
                answer += time - job[0];
            }
        }
        return answer / len;
    }