[프로그래머스/Java] Lv.2 - 프로세스

📝 문제 설명

특정 조건에 따라 프로세스를 실행할 때, 내가 요청한 프로세스가 몇 번째로 실행되는지 구하는 문제입니다.

1. 실행 대기 큐에서 대기 중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기 중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
   • 한 번 실행된 프로세스는 다시 큐에 넣지 않고 종료됩니다.

---

💡 접근 방식

1. 자료구조의 선택

이 문제는 순서 유지(FIFO)와 최대값 탐색이 동시에 필요합니다.

• 일반 Queue: 프로세스의 원래 순서와 위치(location)를 유지하기 위해 사용합니다. Point 객체를 만들어 우선순위와 원래 인덱스를 함께 저장했습니다.
• PriorityQueue (우선순위 큐): 현재 대기열에서 가장 높은 우선순위가 무엇인지 즉각적으로 파악하기 위해 사용했습니다. Collections.reverseOrder()를 사용하여 내림차순(큰 값이 먼저 나오게)으로 설정했습니다.

2. 핵심 로직

1. 큐에서 프로세스(now)를 하나 꺼냅니다.
2. 현재 꺼낸 프로세스의 우선순위가 우선순위 큐의 peek()(최대값)과 일치하는지 확인합니다.
   • 일치하지 않는다면: 뒤에 더 높은 우선순위가 있다는 뜻이므로 다시 일반 큐에 offer()합니다.
   • 일치한다면: 현재 프로세스를 실행합니다.
     • 실행한 프로세스가 내가 찾던 location이라면 즉시 answer를 반환합니다.
     • 아니라면 우선순위 큐에서도 poll()하여 다음 최대값을 준비하고 answer를 증가시킵니다.

---

💻 구현 코드

import java.util.*;

class Point {
    int pri;
    int loc;
    
    public Point(int pri, int loc) {
        this.pri = pri;
        this.loc = loc;
    }
}

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 1;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        Queue<Point> q = new LinkedList<>();
        
        for(int i=0; i<priorities.length; i++) {
            q.offer(new Point(priorities[i], i));
            pq.offer(priorities[i]);
        }
        
        while(!q.isEmpty()) {
            Point now = q.poll();
            
            if(now.pri != pq.peek()) {
                q.offer(now);
            }
            else {
                if(now.loc == location) {
                    return answer;
                }
                pq.poll();
                answer++;
            }
        }
        
        return answer;
    }
}

---

✨ 느낀 점

1. 데이터 중복과 자료구조의 특성
   처음에는 최대값을 관리하기 위해 HashSet을 사용하려 했으나, 우선순위 값은 중복될 수 있다는 점을 간과했습니다. Set은 중복을 제거해버리기 때문에 동일한 우선순위가 여러 개 있을 때 논리적 오류가 발생했습니다. 이를 통해 데이터의 특성(중복 허용 여부)에 따라 올바른 자료구조를 선택하는 것이 얼마나 중요한지 배웠습니다.

2. 효율적인 탐색 (for vs peek)
   우선순위 큐를 단순 순회(for)하며 최대값을 찾는 방식에서 peek()을 사용하는 방식으로 최적화했습니다. PriorityQueue의 힙(Heap) 구조 덕분에 최대값을 $O(1)$의 시간 복잡도로 즉시 확인할 수 있다는 장점을 제대로 활용해 볼 수 있었던 경험이었습니다.

3. 객체를 통한 상태 관리
   Point 클래스를 별도로 정의하여 priority와 location을 묶어서 관리하니, 큐가 변하더라도 데이터의 무결성을 지킬 수 있어 코드가 훨씬 직관적으로 변했습니다.