<java> 프로그래머스 디스크 컨트롤러 : 우선순위 큐

 

https://tmdrnr96.tistory.com/32

[Data Structure] 우선순위 큐(Priority Queue)란?

 

문제를 보자마자 우선 순위 큐를 써야 겠다는 생각이 들었다.

 

그리고 최근 다짐했던 것 처럼 문제 설계도 미리 했다.

하지만 코드를 보면서 느낀점은 아주 비효율적으로 문제를 풀고 있다는 점이다.
지금 시작하는 일들 대기열에 집어 넣기 부분이 아주 비효율 적으로 느껴졌다.

후에 개선 하고 싶다면 특히 저 부분을 확실히 개선 해야 할 것이다.

처음 설계 방향

요청시간에 진행 중인 일이 없을때 지금 한다
요청시간에 진행 중인 일이 있을때 대기에 걸어둔다
요청 시간에 진행중인 일이 끝나면 대기에 잇는것 중 가장 짧은 일을 가장 먼저 한다 pq 사용
같은 시간이 걸리면 먼저 들어온 일부터 한다

우선순위 큐 (Priority Queue) 개념 및 구현

---

일반적인 큐(Queue): 먼저 집어넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장하는 선형 자료구조

우선순위 큐(Priority Queue): 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조

 

데이터를 추가할때 ,우선순위를 기준으로 최소힙, 또는 최대 힙을 구성하고 데이터를 꺼낼 때, 루트 노드를 얻어낸 뒤에 루트 노드를 삭제할때는 빈 루트 노드 위체에 마지막 노드를 삽입한 후에 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행됨

 

우선순위 큐는 항상 정해진 우선순위에 맞게 정렬된 상태에서 데이터를 추가하거나 빼기 때문에 우선 순위를 중시하는 문제에서 유용하게 사용됨,

내부 구조가 힙구조 이므로 o(NlogN)의 시간 복잡도를 가진다

 

 

정답

import java.util.*;
import java.io.*;

class Solution {
    public int solution(int[][] jobs) {
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) ->
                                                     o1[1] - o2[1]);
        
        //maxTime get
        int maxStartTime = 0;
        int maxEndTime = 0;
        for(int[] job : jobs){
            maxStartTime = Math.max(maxStartTime, job[0]+1);    
            maxEndTime += job[1];    
        }
        maxEndTime += maxStartTime;

        //요청시간에 진행 중인 일이 없을때 지금 한다
        //요청시간에 진행 중인 일이 있을때 대기에 걸어둔다
        //요청 시간에 진행중인 일이 끝나면 대기에 잇는것 중 가장 짧은 일을 가장 먼저 한다 pq 사용
        //같은 시간이 걸리면 먼저 들어온 일부터 한다
        
        List<Integer> workList = new ArrayList<>();
        for(int i = 0; i< maxEndTime; i++){
            workList.add(-1);
        }
        Queue<int[]> jobList = new LinkedList<>();
        for(int i = 0; i < jobs.length; i++){
            jobList.add(new int[]{jobs[i][0], jobs[i][1], i});
        }

        int time = 0;
        while(time != maxEndTime){
            Queue<int[]> temp = new LinkedList<>();
            while(!jobList.isEmpty()){// 지금 시작하는 일들 대기열에 집어넣기
                int[] work = jobList.poll();
                if(work[0] == time){
                    pq.add(work);
                }else{
                    temp.add(work);
                }
            }
            jobList.addAll(temp);
            
            if(workList.get(time) == -1){//현재 일을 안함
                if(pq.isEmpty()){//할일이 없다
                    time++;
                    continue;
                }else{// 일이 있다
                    int[] work = pq.poll();
                    for(int i = 0; i< work[1]; i++){// 일한 시간 세팅
                        // System.out.println(work[2]);
                        workList.set(time + i, work[2]);
                    }
                }
            }
            time++;
        }
                    
        int preIndex = -1;
        int count = 0;
        for(int i = 0; i< maxEndTime; i++){
            if(workList.get(i) != -1){
                int index = workList.get(i);
                if(index == preIndex){
                    continue;
                }else{
                    count += i - jobs[index][0] + jobs[index][1] ;
                    preIndex = index;                    
                }
            }
        }
        
        int answer = count/ jobs.length;
        return answer;
    }
}