[프로그래머스 알고리즘 고득점 Kit][스택/큐][Java] 프로세스

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

프로그래머스

이 문제의 핵심은 큐의 순서를 유지하면서도, 현재 프로세스보다 우선순위가 높은 프로세스가 남아 있는지 판단하는 것이다.

처음에는 큐를 직접 순회하면서 더 높은 우선순위가 있는지 확인할 수도 있다. 하지만 이 문제에서는 우선순위가 1부터 9까지로 제한되어 있다. 따라서 각 우선순위의 남은 개수를 배열로 관리하면, 현재 프로세스가 실행 가능한지 더 간단하게 판단할 수 있다.

각 프로세스는 우선순위와 원래 위치를 함께 가진 객체로 저장했다. 큐에서 프로세스의 위치는 계속 바뀌지만, 원래 location을 알아야 목표 프로세스가 몇 번째로 실행되는지 판단할 수 있기 때문이다.

프로세스를 하나 꺼낸 뒤, 현재 우선순위보다 높은 우선순위가 아직 남아 있다면 다시 큐의 뒤에 넣는다. 그렇지 않다면 해당 프로세스를 실행하고, 실행 횟수를 증가시킨다. 실행한 프로세스의 원래 위치가 문제에서 주어진 location과 같다면 그때의 실행 횟수가 정답이 된다.

이 풀이의 장점은 문제의 제약을 활용했다는 점이다. 우선순위 범위가 1~9로 고정되어 있으므로, 매번 큐 전체를 확인하지 않고 우선순위 개수 배열만 확인해도 된다.

정답 코드

import java.util.*;

class Solution {
    
    public class Process {
        int priority;
        int firstLocation;
        
        Process(int priority, int firstLocation) {
            this.priority = priority;
            this.firstLocation = firstLocation;
        }
    }
    
    public int solution(int[] priorities, int location) {
        Queue<Process> q = new ArrayDeque<>();
        
        int len = priorities.length;
        int[] prioritiesCount = new int[10];

        for(int i=0; i<len; i++) {
            int p = priorities[i];
            q.add(new Process(p, i));
            prioritiesCount[p] += 1;
        }
        
        int answer = 0;
        while(!q.isEmpty()) {
            Process process = q.poll();
            
            if(!isHighestPriority(process.priority, prioritiesCount)) {
                q.add(process);
            } else {
                answer += 1;
                prioritiesCount[process.priority] -= 1;
                
                if(process.firstLocation == location) return answer;
            }
            
        }

        return answer;
    }
    public boolean isHighestPriority(int p, int[] prioritiesCount) {
        for(int s = p+1; s<=9; s++) {
            if(prioritiesCount[s] > 0) return false;
        }
        
        return true;
    }
}