[Java] 프로그래머스 : 프로세스

[Java] 프로그래머스 : 프로세스

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

프로그래머스

---

접근

2번째 테스트 케이스를 보면 가장 처음 인덱스에 있는 값이 5번째로 실행되는 것을 확인할 수 있다.

9다음 1이 다음 우선순위가 되도록 하기 위해서 가장 먼저 떠올린 것은, priorities를 내림차순 정렬한 배열을 하나 더 만드는 것이었다.

 

큐에는 priorities 원본 배열 값을 전부 집어 넣고, 내림차순된 배열의 값과 큐의 특정 값이 일치하는 경우 answer를 하나씩 올리고,

만약 location번째의 값이었을 경우 정답을 출력할 수 있도록 구현하였다.

 

import java.util.*;

class Position {
    int priority;
    int idx;

    Position(int priority, int idx) {
        this.priority = priority;
        this.idx = idx;
    }
}

class Solution {
    public int solution(int[] priorities, int location) {
        
        int answer = 0;
        Queue<Position> q = new LinkedList<>();
        int[] temp = Arrays.copyOf(priorities, priorities.length);
        Integer[] priArr = Arrays.stream(temp).boxed().toArray(Integer[]::new);
        Arrays.sort(priArr, Collections.reverseOrder());
        
        for (int i = 0; i < priorities.length; i++) {
            q.offer(new Position(priorities[i], i));
        }
        
        int idx = 0;
        while (!q.isEmpty()) {
            Position pos = q.poll();
            
            if (pos.priority == priArr[idx]) {
                answer++;
                idx++;
                
                if (pos.idx == location) {
                    break;
                }
            }
            else {
                q.offer(pos);
            }
        }
        return answer;

    }
}

그러나 위의 방법은 큐에 들어갈 값들의 위치를 기억하기 위한 메모리가 필요할 뿐만 아니라, 내림차순 배열을 만들기 위해 배열 복사까지 해야했기 때문에 개선이 필요했다.

 

먼저, 내림차순 배열을 하나 더 만드는 부분을 우선순위 큐를 선언하여 자동으로 내림차순 되는 큐를 만드는 방식으로 변경했다.

기존에는 배열을 내림차순 한 후, 큐를 계속 순회하면서 값이 일치하는 경우를 찾았으나, 이번에는 큐가 자동으로 내림차순 정렬되어 있기 때문에 기존 배열에서 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 p : priorities) {
            pq.add(p);
        }
        
        while(!pq.isEmpty()) {
            for (int i = 0; i < priorities.length; i++) {
                if (priorities[i] == pq.peek()) {
                    pq.poll();
                    answer++;
                    
                    if (i == location) {
                        return answer;
                    }
                } 
            }
        }
        return answer;
    }
}