[프로그래머스/Java] 42587 프로세스

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

프로그래머스

 

고찰 과정

문제를 봤을 때 단순하게 우선순위 큐를 활용하는 방법도 있겠지만 추가적인 확인 작업도 필요했기에 deque를 활용하여 문제를 해결했습니다.

예를 들어서 프로세스 [A, B, C, D, E, F]가 존재하고 우선순위가 [1, 1, 9, 1, 1, 1]이 있을 때 A의 순서 번호를 구한다고 가정해봅시다.

당연히 C가 먼저 실행되지만 그 다음 실행되어야 하는 순서는 A, B, D, E, F 순이 아닌 C가 실행한 이후의 실행 순서를 마무리 한 후인 D, E, F, A, B 순으로 실행이 되어야 하므로 이를 deque를 활용하면 다음과 같은 순서로 A의 순번을 도출할 수 있습니다.

1. priorities 배열에서 특정 우선순위가 몇 번 나왔는지 저장하는 배열 priorityInfos를 만들고 정보를 저장한다.
2. priorityInfos 배열을 꺼내어 deque에 담는다.
3. 다음과 같은 순서로 A의 순서를 도출한다.
   a. deque에서 맨 앞(왼쪽)의 우선순위 정보를 꺼낸다.
   b. priorityInfos를 활용하여 이 우선순위 보다 큰 우선순위가 존재하는지 확인한다. 존재한다면 deque의 맨 마지막(오른쪽)에 다시 넣어주고 최고 우선순위라면 순번을 카운트 해주고 priorityInfos에서 해당 우선순위의 존재 개수에서 하나 빼준다.
   

위의 과정들을 코드로 작성하면 됩니다.

 

---

코드

import java.util.*;

class Process {
    private final int index;
    private final int priority;
    
    public Process(int index, int priority) {
        this.index = index;
        this.priority = priority;
    }
    
    public int getIndex() {
        return index;
    }
    
    public int getPriority() {
        return priority;
    }
}

class Solution {
    
    private static final int MAX_VALUE = 10;
    
    public int solution(int[] priorities, int location) {
        int answer = 0;
        int pLen = priorities.length;
        int[] priorityInfos = new int[MAX_VALUE];
        
        for (int priority : priorities) {
            ++priorityInfos[priority];
        }
        
        Deque<Process> deque = new ArrayDeque<>();
        
        for (int i = 0; i < pLen; ++i) {
            deque.addLast(new Process(i, priorities[i]));
        }
        
        while (!deque.isEmpty()) {
            Process process = deque.pollFirst();
            int curIdx = process.getIndex();
            int curPriority = process.getPriority();
            
            if (existMorePriority(curPriority, priorityInfos)) {
                deque.offerLast(new Process(curIdx, curPriority));
                continue;
            }
            
            ++answer;
            
            if (curIdx == location) {
                break;
            }
            
            --priorityInfos[curPriority];
        }
        
        return answer;
    }
    
    private boolean existMorePriority(final int priority, final int[] priorityInfos) {
        for (int curP = priority + 1; curP < MAX_VALUE; ++curP) {
            if (priorityInfos[curP] > 0) {
                return true;
            }
        }
        
        return false;
    }
}