[프로그래머스/Java] 프로세스 Queue (+PriorityQueue)

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

프로그래머스

 

내 풀이

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0, result = -1;
        Queue<int[]> queue = new LinkedList<>();
        
        for(int i=0; i<priorities.length; i++){
            queue.offer(new int[]{i, priorities[i]});
        }
        
        while(result != location){
            
            int[] current = queue.poll();
            boolean flag = false;
            
            for(int[] q : queue){
                if(q[1] > current[1]){
                    flag = true;
                    break;
                }
            }
            
            if(flag){
                queue.offer(current);
            } else {
                result = current[0];
                answer++;
            }
        }
        
        
        return answer;
    }
}

 

PriorityQueue를 활용한 최적화 코드

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        
        // 1. 일반 큐: [처음 위치, 우선순위] 저장
        Queue<int[]> queue = new LinkedList<>();
        // 2. 우선순위 큐: 높은 숫자(우선순위) 순으로 자동 정렬 (내림차순)
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        for (int i = 0; i < priorities.length; i++) {
            queue.offer(new int[]{i, priorities[i]});
            pq.offer(priorities[i]);
        }
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            
            // pq.peek()은 현재 남아있는 프로세스 중 '가장 높은 우선순위'를 말합니다.
            if (current[1] < pq.peek()) {
                // 더 높은 우선순위가 존재하므로 맨 뒤로 보냅니다.
                queue.offer(current);
            } else {
                // 현재 꺼낸 것이 가장 높은 우선순위이므로 실행(인쇄)합니다.
                pq.poll(); // 실행되었으므로 우선순위 큐에서도 제거
                answer++;  // 차례 카운트
                
                // 실행한 프로세스가 내가 찾던 위치(location)라면 종료!
                if (current[0] == location) {
                    break;
                }
            }
        }
        
        return answer;
    }
}