문제출처

프로그래머스 코딩테스트 연습 > 스택/큐 > 프로세스

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

문제설명

프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스 위치 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return하도록 한다.

규칙은 다음과 같다.

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

접근 방법

사실 해당 문제는 문제 속에 답이 있다. "큐(Queue)" , "우선순위"를 통해 프로세스가 몇 번째로 실행되는지 알아내라. 즉, "우선순위 큐"를 사용하라는 의미로 해석할 수 있다. 또한, 규칙에서 어떻게 구현하면 되는지 1~3(3.1)까지 과정도 자세하게 알려준다.

일단 answer은 프로세스가 실행되는 횟수라고 가정한다.
우선순위 큐에 프로세스들을 넣고, priorities 배열과 우선순위 큐의 요소들을 비교하면서 프로세스가 실행될 때마다 answer을 1씩 증가시킨다.
해당 과정에서 priorities 의 인덱스가 location과 같아질 때가 목표하는 프로세스가 실행되는 순번이다.

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int a : priorities){
            pq.add(a);
        }
        while(!pq.isEmpty()){
            for(int i =0; i< priorities.length; i++){
                if(priorities[i] ==pq.peek()){
                    pq.remove();
                    answer++;
                    if(i == location){
                        return answer;
                    }
                }
            }
        }
        return answer;
    }
}

알게된 점

사실 나는 이 문제를 잘 풀지 못했다. 처음 일반적인 큐를 통해 풀려고 접근했으나, 일반적인 큐는 정말 priorities의 요소 값들을 그대로 집어넣기 때문에 우선순위에 따라 정렬이 되지 않으므로 다른 정제의 과정이 필요하다. 그래서 우선순위의 큐를 통해 priorities를 정제하고 풀어가는 방법이 편하다는 것을 알았다.

추가로, 다른 사람들이 '큐(Queue)'를 통해 푼 것을 확인했는데 이는 "조건에 따라 location의 값을 조정하면서 location의 값이 음수가 될 때, 원하는 프로세스가 실행된다." 방식으로 푼다는 것을 확인했다. 주말에 정리하면서 다시 풀어볼 예정이다.

문제푼 흔적