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

대기 큐에서 프로세스를 하나씩 꺼내서 더 높은 우선순위가 뒤에 있으면 다시 뒤로 보내고,
없으면 실행할 때 내가 찾는 프로세스가 몇 번째로 실행되는지 구하는 문제.

 

1. 문제 유형

큐, 구현, 시뮬레이션

 

2. 내가 놓친 포인트

처음 떠올린 접근 : 맨 앞 값을 꺼낸 뒤에 배열을 순회하면서 더 큰 값이 있으면 그 값으로 넘어가고, 실행한 값은 0으로 바꾸는 식으로 생각했다.

오답 원인: 이 문제는 단순히 큰 값을 찾는 문제가 아니라 큐의 순서를 그대로 시뮬레이션해야 하는 문제였다.
또한 처음 location 위치에 있던 프로세스 자체를 끝까지 추적해야 했다.
queue의 사용법과 queue<int[]>가 가능하다는 사실을 몰랐기 때문에 푸는게 오랜 시간이 걸렸다.

 

3. 핵심 로직 & 해결 방법

핵심 조건: 현재 맨 앞 프로세스보다 더 높은 우선순위가 큐 뒤에 하나라도 있으면 그 프로세스는 실행되지 않고 다시 큐의 맨 뒤로 간다. 더 높은 우선순위가 없을 때만 실행되고 이때 실행 순서를 1 증가시킨다.

풀이 아이디어:

1. 큐에 우선순위만 넣지 말고, [우선순위, 원래 위치] 형태로 함께 저장한다.
2. 큐의 맨 앞 프로세스를 하나 꺼낸다.
   그리고 남아 있는 큐 전체를 확인해서 현재 프로세스보다 더 높은 우선순위가 있는지 검사한다.
3. 더 높은 우선순위가 있다면 현재 프로세스를 다시 큐 뒤에 넣고 없다면 실제로 실행하므로 count++ 한다.
   이때 방금 실행한 프로세스의 원래 위치가 location이면 그 순간의 count를 반환한다.

4. 구현 코드

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        Queue<int[]> q = new LinkedList<>();
        for(int i = 0; i < priorities.length; i++){
            int[] process = {priorities[i], i};
            q.offer(process);
        }
        
        int count = 0;
        
        while(!q.isEmpty()){
            int[] first = q.poll();
            boolean hasHigher = false;
            
            for(int[] process : q){
                if(process[0] > first[0]){
                    hasHigher = true;
                    break;
                }
            }
            
            if(hasHigher) {
                q.offer(first);
            } else {
                count++;
                if(first[1] == location){
                    return count;
                }
            }
        }
        return count; 
        
    }
}

시간 복잡도: O(N²) / 공간 복잡도: O(N)

 

---

 

인사이트

• 정렬 문제가 아니라 큐를 직접 시뮬레이션하는 문제
• 값만 추적하면 헷갈리고 우선순위 + 원래 위치를 함께 묶어야 구현이 편해진다.
• 문제 이해와 풀이 아이디어는 맞았지만, 실제 구현에서는 Queue<int[]> 같은 자바 표현 방식이 익숙하지 않아 막혔다.
• Queue<> 안에 int[]대신 커스텀 클래스도 사용 가능하다.

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/42587