[Algorithm] Programmers_프로세스 in Java

💡 Programmers Level.2 프로세스:

작업대기열에서 location에서 위치하는 프로세스가 몇번째로 실행되는 프로세스인지 찾기

🌱 코드 in Java

알고리즘: Queue

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 1;
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        for (int i = 0; i < priorities.length; i++)
            pq.add(priorities[i]);
        
        while (!pq.isEmpty()) {
            for (int i = 0; i < priorities.length; i++) { // 우선순위 배열 순회
                if (priorities[i] == pq.peek()) { // 작업이 가능한 프로세스인지 확인
                    if (i == location) // 찾는 프로세스인지 확인
                        return answer;
                    pq.poll();
                    answer++;
                }
            }
        }
        return answer;
    }
}

이번 문제는 사실 처음에는 아래처럼 풀었다.

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {      
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        Queue<int[]> q = new ArrayDeque<>();
        
        for (int i = 0; i < priorities.length; i++) {
            pq.add(priorities[i]);
            q.add(new int[]{priorities[i], i});            
        }
        int cnt = 1;
        while (!pq.isEmpty()) {
            int need = pq.poll();
            int[] now = q.poll();
            while (now[0] != need) { // 실제로 큐에 넣고 프로세스를 돌리기
                q.add(now);
                now = q.poll();
            }
            if (now[1] == location)
                return cnt;
            cnt++;
        }
        return cnt;
    }
}

처음 문제를 보고 priorities에 들어있는 프로세스들의 위치를 어떻게 기억하지? 라고 생각했다.
원형배열을 구현해야하나? 거기서 쭉 돌려야 하나? 어떻게하지? 싶어서
처음 생각해 낸 방법이 index와 priority를 배열로 한 큐를 만들어서
실제로 계속 작업대기큐를 돌리는 방식으로 구현을 했다.

그러나 첫번째 코드처럼 안에서 priority배열을 순회하면 원형배열과 같은 효과를 얻는 것이었다.
일치 하는 애 다음부터 찾게 되고 배열 범위 안에서 순회하니..
이거보다 깔끔한 풀이가 있을까 싶을 정도.

우선순위 배열을 정렬한다음에 location을 줄여가며 푸는 방법도 있던데,
이런 index가지고 처리해야하는 것들에 대해서 내가 조금 더 생각했으면 좋겠다.

🧠 기억하자

1. Java Queue

• Priorityqueue
• ArrayDeque
• LinkedList
• Queue<>(Collections.reverseOrder())와 같이 comparator를 넣어줄 수 있다