[프로그래머스] Lv.2 프로세스 (PriorityQueue, poll(), offer() ,Java)

 

문제설명

입력 & 출력

나의 풀이

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
  3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.

 

이번 문제는 위와 같은 규칙에 따라 각 프로세스의 우선순위를 고려하여 특정 프로세스가 몇 번째로 실행되는지 계산해야 합니다.

 

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int n : priorities){
            queue.offer(n);
        }
        
        int idx = 0;
        while(!queue.isEmpty()){
            for(int i = 0 ; i < priorities.length ; i++){
                if(priorities[i] == queue.peek()){
                    System.out.println(i + " " + queue.peek());
                    queue.poll();
                    idx++;
                    
                    if(i == location){
                        return idx;
                    }
                }
            }
        }

        return idx;
    }
}

 

문제의 접근방식은 다음과 같습니다.

 

프로세스 [A,B,C,D]가 있고, 해당 프로세스의 각 우선순위를 입력받습니다. [2,1,3,2] 그러면 각 프로세스의 우선순위는 다음과 같습니다.

 

• A ➡ 2순위
• B ➡ 1순위
• C ➡ 3순위
• D ➡ 2순위

그리고 몇번째로 실행되는지 알고싶은 프로세스의 위치 location이 주어집니다. 예제1번에서는 location : 2입니다.

 

그러면 궁극적으로 알고싶은 2번인덱스는 C로 우선순위에 따라서 C➡ D ➡ A➡ B 순으로 실행되기 때문에 1번째에 실행됩니다. 따라서 최종 반환값은 1이됩니다.

 

정리하자면 우선순위에 따라 실행되는 프로세스 중에서 location에 위치하는 프로세스가 몇번째에 실행되는지 알아내면 되는 문제입니다.

 

예제1번을 보면 우선순위가 존재하며 우선순위가 중복이 존재하기 때문에 우선순위 큐를 사용하면 간단히 풀 수 있습니다.

---

먼저 PriorityQueue를 선언합니다. 이 때 PriorityQueue는 기본적으로 작은 값이 우선순위가 높은 형태인 오름차순(최소 힙)입니다. 따라서 문제에서는 큰 값이 우선순위가 높기 때문에 내림차순(최대 힙)으로 정렬해야 합니다.

 

따라서 Collections.reverseOrder() 메서드를 사용하여 큐를 내림차순으로 정렬할 수 있도록 설정해줍니다. 그리고 향상된 for문을 사용하여 원래의 우선순위 배열을 넣게되면 [2,1,3,2] ➡ [3,2,2,1]로 형성되게 됩니다.

 

그리고 큐의 isEmpty() 메서드를 사용하여 큐의 값이 존재할때 계속 반복해주는 while문을 선언하고, 기존 우선순위 배열에 접근을 해줍니다.

 

기존 우선순위 priorities 배열의 요소를 계속해서 순회하면서 큐의 peek()메서드를 사용하여 큐의 우선순위가 높은 요소를 조회하여 같다면 해당 큐의 요소를 poll()메서드로 삭제해주고, 인덱스 idx값을 증가시켜줍니다.

 

그리고 만약에 기존 프로세스 우선순위의 배열의 인덱스 i 와 내림차순으로 정렬한 우선순위의 인덱스가 같다면 해당 프로세스의 인덱스 즉 실행순서를 반환해줍니다.

 

간단히 정리하자면

1. 배열을 순회하면서 우선순위가 가장높은 프로세스를 찾는다.
2. 우선순위가 가장 높은 프로세스인 경우 큐에서 프로세르를 제거한다.
3. 실행 순서를 증가시킨다.
4. 만약 찾고자하는 location의 프로세스인 경우에 현재 실행순서를 반환한다.

첫번째 예시를 예로 들자면 동작 순서는 다음과 같습니다.

 

• queue.peek()는 3을 반환합니다.
• priorities[0]은 2이므로 조건이 맞지 않습니다.
• priorities[1]은 1이므로 조건이 맞지 않습니다.
• priorities[2]는 3이고, queue.peek()과 일치합니다.
• 큐에서 3을 제거하고 idx를 1로 증가시킵니다.
• i == location이므로 idx를 반환합니다.

 

 

 

참고 ❗

 

[자료구조 JAVA] 우선순위 큐(Priority Queue) 클래스 알아보기 ✔

[자료구조 JAVA] 우선순위 큐(Priority Queue) 클래스 알아보기 ✔