섹션3. 자료구조 활용 섹션 -(4)

🎈섹션3. 자료구조 활용 섹션 -(4)

⬛ 우선순위 큐 | Priority Queue

• 큐(Queue)는 FIFO 의 형태로 데이터를 처리한다.
• Priority Queue 는 우선순위를 먼저 결정한 뒤, 그 우선순위가 높은 요소부터 먼저 나가는 자료구조이다.

import java.util.PriorityQueue; //import

//int형 priorityQueue 선언 (우선순위가 내부 값 오름차순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//int형 priorityQueue 선언 (우선순위가 내부 값 내림차순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

//String형 priorityQueue 선언 (우선순위가 내부 값 오름차순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 

//String형 priorityQueue 선언 (우선순위가 내부 값 내림차순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

---

🟦 3-5. CPU 스케쥴링

문제 풀이

• 이 문제는 조건 중에서 대기 상태 작업이 많을 경우 실행 시간이 적은 순으로 , 실행 시간이 같은 경우 작업 번호가 적은 순으로 작업을 먼저 처리해야 한다는 ‘우선순위’를 걸어두었다.
• 이런 우선순위가 존재하는 문제에는 Priority Queue 우선순위 큐를 사용해야 한다.

완성 코드

/* 3-5. CPU 스케쥴링 문제 풀이 */
import java.util.*;
class Solution1 {
    //솔루션 함수 
    public int[] solution(int[][] tasks){
        int n = tasks.length;
        int[] answer = new int[n];

        LinkedList<int[]> programs = new LinkedList<>();
        for(int i = 0; i < n; i++){
                        //(각 i의 0번쨰 (호출시간), 1번쨰 (작업시간), n번 작업번호 ) 를 ArrayList에 담는다. 
            programs.add(new int[]{tasks[i][0], tasks[i][1], i});
        }
        programs.sort((a, b) -> a[0] - b[0]);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        int fT = 0, idx = 0;
        while(!programs.isEmpty() || !pq.isEmpty()){
            if(pq.isEmpty()) fT = Math.max(fT, programs.peek()[0]);
            while(!programs.isEmpty() && programs.peek()[0] <= fT){
                int[] x = programs.pollFirst();
                pq.add(new int[]{x[1], x[2]});
            }
            int[] ex = pq.poll();
            fT = fT + ex[0];
            answer[idx++] = ex[1];
        }    
        return answer;
    }

    //실행 메인 
    public static void main(String[] args){
        Solution1 T = new Solution1();
        System.out.println(Arrays.toString(T.solution(new int[][]{{2, 3}, {1, 2}, {8, 2}, {3, 1}, {10, 2}})));
        System.out.println(Arrays.toString(T.solution(new int[][]{{5, 2}, {7, 3}, {1, 3}, {1, 5}, {2, 2}, {1, 1}})));
        System.out.println(Arrays.toString(T.solution(new int[][]{{1, 2}, {2, 3}, {1, 3}, {3, 3}, {8, 2}, {1, 5}, {2, 2}, {1, 1}})));
        System.out.println(Arrays.toString(T.solution(new int[][]{{999, 1000}, {996, 1000}, {998, 1000}, {999, 7}})));
    }
}

---