[프로그래머스] 프로세스 (Queue)

문제 소개

오늘 풀었던 프로그래머스 - 프로세스 문제를 정리합니다.

이 문제는 운영체제가 여러 프로세스를 우선순위에 따라 처리할 때, 특정 프로세스가 몇 번째로 실행되는지를 파악하는 문제입니다.

문제 링크: 프로세스 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 해결합니다:

1. 프로세스를 (인덱스, 우선순위) 형태로 큐에 저장
2. 현재 큐에서 하나 꺼내고,
   큐 안에 더 높은 우선순위가 있으면 다시 뒤로 넣고 / 아니면 실행 처리
3. 실행 횟수를 카운트하면서, 현재 실행한 프로세스가 내가 찾는 location이면 종료

---

해결 과정 및 코드

핵심 아이디어

1. 프로세스를 (index, priority) 형태로 큐에 저장
2. 실행 순서를 세기 위해 높은 우선순위부터 비교
3. 실행 순서 = 정렬된 우선순위 배열에서 뒤에서부터 매칭

코드

시간 복잡도 : O(N²)

• 큐 삽입: O(N) + 정렬: O(N log N) + 큐 순회 및 처리: 최악 O(N²) (하지만 실제 평균은 훨씬 빠름)

 

import java.util.*;

public class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;

        ArrayDeque<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < priorities.length; i++) {
            queue.offer(new int[]{i, priorities[i]});
        }

        Arrays.sort(priorities); // 우선순위 큰 순으로 뒤에서부터 사용
        int priorityIndex = priorities.length - 1;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            if (current[1] == priorities[priorityIndex - answer]) {
                answer++;
                if (current[0] == location) break;
            } else {
                queue.offer(current); // 우선순위 낮으면 다시 큐 뒤로
            }
        }

        return answer;
    }
}