1. 문제에 대하여 📦

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

(1) 조건 분석 📊

각 프로세스는 무조건 우선순위가 높은 순으로 실행된다.
이때 인수로 주어진 숫자가 원래 대기 큐 상 위치인 프로세스가 실행되는 순서는 언제일까?

2. 코드가 나오기까지 🛠️

KEY WORD: 큐 활용

프로세스의 실행 우선순위가 높은 것부터 내림차순한 우선순위 큐 만들기
(우선순위 큐는 '실행 대기 중인 프로세스 중 우선순위가 높은 순' 이다.
프로세스의 원래 위치를 담은 일반 큐 만들기
우선순위 큐의 peek()의 우선순위 == 프로세스의 poll()의 우선순위이면, 현재 프로세스 실행해도 된다. 이때 해당 프로세스는 이미 실행 후 종료했으므로, 우선순위 큐에서도 제거한다.
만약 2번이 안되면 poll()한 프로세스를 다시 일반 큐 꼬리에 넣는다.
(1) 시간복잡도 분석 ⏳

시간복잡도적 분석이 필요 없는 문제였다.

3. 코드 🌐

import java.util.*;

class Solution {
    static class Ps {
        int p; // 우선순위
        int ol; // 원래 번호

        public Ps(int p, int ol) {
            this.p = p;
            this.ol = ol;
        }
    }

    public int solution(int[] priorities, int location) {
        PriorityQueue<Ps> pg = new PriorityQueue<>((p1,p2) -> (p2.p - p1.p));
        ArrayDeque<Ps> os = new ArrayDeque<>();

        for(int i = 0; i < priorities.length; i++){
            Ps now = new Ps(priorities[i], i);
            pg.add(now);
            os.add(now);
        }
        int num = 0;
        while(!os.isEmpty()){
            Ps top = pg.peek();
            Ps now = os.poll();
            if(top.p == now.p) {
                pg.poll();
                num++;
                if(now.ol == location) return num;
            }else{
                os.add(now);
            }
        }
        return num;
    }
}