[프로그래머스] 프로세스 (우선순위큐)

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

 

풀이과정

1. 우선순위가 가장 높은 프로세스를 찾아야 합니다. 👉우선순위 큐를 활용 O(logn)하여 구할 수 있습니다.

 

2. 문제의 2번 조건을 구현해야 합니다.

2번 조건의 동작에서 다시 큐에 넣는 원소들의 순서는 유지됩니다.

위 그림과 같이 (2,1)은 뒤로 가야하는데 이때 뒤로 가는 (2,1)의 순서는 유지됩니다.

따라서 큐를 활용해서 구현할 필요 없이 주어진 priorities 배열들을 순서대로 무한순회(?)하면 됩니다.

 

3. 문제에서 요구하는 정답인 해당 프로세스가 몇 번째로 실행되는지 파악해야 합니다.

배열들을 무한순회(2번 풀이과정) 하며 우선순위가 가장 높은 프로세스(1번 과정)와 일치하면 해당 프로세스는 실행되므로 answer을 +1해줍니다.

 

이때 location과 실행되는 프로세스의 인덱스가 같으면 문제에서 요구하는 프로세스를 찾은 것이므로 함수를 종료합니다.

 

배운점

• 우선순위에 대한 문제에서 우선순위큐를 요긴하게 활용할 수 있음을 알게되었습니다.
• 프로세스들을 큐를 활용하지 않고, 배열을 무한순회 하는 방식으로 구현할 수 있음을 알게되었습니다.
• 우선순위 큐에 remove함수를 사용할 수 있습니다. 이때 remove함수의 시간복잡도는 O(n) 입니다.

 

 

전체코드

import java.util.*;

class Solution {
    
    int answer;
    
    void solve(int[] priorities,int location){
        
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2)->-(o1-o2));
        
        for(int i=0;i<priorities.length;i++){
            pq.offer(priorities[i]);
        }
        
        while(!pq.isEmpty()){
            
            for(int i=0;i<priorities.length;i++){
                
                if(priorities[i]==pq.peek()){
                    answer++;
                    pq.poll();
                    
                    if(i==location) return;
                }
            }
        }
        
    }
    
    
    public int solution(int[] priorities, int location) {
        answer = 0;
            
        solve(priorities,location);
        
        return answer;
    }
}