프로세스

작성일: 2024-11-07

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

접근 방식

priority 배열에 순서대로 처리해야 할 프로세스들의 우선순위가 들어있기에

해당 원소들의 인덱스 위치와 우선순위를 하나의 배열로 만들어서, 우선순위큐를 이용해 우선순위 기준 내림차순 정렬했다.

그리고, 큐에서 하나씩 꺼내며 주어진 location과 일치하는 인덱스 위치를 가진 배열의 순서를 리턴했다.

잘못된 접근

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        PriorityQueue<int[]> que = new PriorityQueue<>((a, b) -> b[1] - a[1]); // 우선순위 기준 내림차순
        int idx = 0;
        for(int p:priorities) que.offer(new int[] {idx++, p});
        int answer = 0;
        while(!que.isEmpty()){
            int[] cur = que.poll();
            answer++;
            if(cur[0]==location) break;
        }

        return answer;
    }
}

위의 로직에는 문제가 있다.
값이 같은 경우는 정렬기준이 정해지지 않았을 뿐만 아니라, 값이 같은 경우에 단순하게 내림차순, 오름차순으로 정렬한다고 해결되지 않는다.

예를 들어서, {1, 1, 1, 1, 1} 과 같은 배열이 존재하고, 4번 인덱스의 실행 순서를 알고자 한다면, 모두 값이 같으므로 정렬 순서를 보장하지 않는다. 따라서 실행시마다 다른 값들이 출력될 수 있는 것이다.

이를 위해서는 큐를 하나 추가해서 해결 할 수 있다.

결과

소스 코드

import java.util.*;
class Solution {
    public int solution(int[] priorities, int location) {
        Queue<int[]> q = new LinkedList<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b-a);

        for(int i = 0; i < priorities.length; i++) {
            q.offer(new int[] {i, priorities[i]});
            pq.offer(priorities[i]);
        }

        int answer = 0;
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            if(cur[1] < pq.peek()){
                q.offer(cur);
            }else{
                answer++;
                pq.poll();
                if(cur[0]==location) break;
            }
        }
        return answer;
    }
}

먼저 큐에 기존 배열의 순서대로 값을 넣는다. 우선순위큐는 내림차순 정렬을 설정하고 우선순위를 넣는다.

그 다음은 큐에 들어있는 값들을 하나씩 처리하는데, 현재의 값이 우선순위큐에 있는 최댓값보다 작다면 다시 큐에 집어넣는다.

같다면, 우선순위큐에 값을 제거하는데, (최댓값이므로)
현재 큐에서 나온 값의 순서가 주어진 location과 같다면 while문을 종료한다.

이렇게 되면 우선순위의 크기가 큰 순서부터 출력하다가, 같은 경우에는 (작은 경우는 존재하지 않는다. 내림차순 정렬이기에) 해당 값의 위치를 리턴하게 되는 것이다.

다른 접근 방식

없음.

알게 된 점

없음.