프로그래머스 - 프로세스 (JAVA)

프로그래머스 프로세스 풀이 과정
3시간을 헤매다 결국 과거에 통과했던 나의 코드를 참고해서 겨우 통과했다.
점수 흐름: 60 → 45 → 40 → 60 → 100
총 5번의 제출

---

1트 (오답)

이 문제를 처음 봤을 때 떠올린 건 우선순위 큐였다. 우선순위가 높은 것부터 처리한다는 문장만 보고, Comparable을 구현한 Process 클래스를 만들어 우선순위 내림차순으로 정렬해서 꺼내면 되겠다고 판단했다. PriorityQueue에서 꺼내는 순서가 곧 실행 순서라고 본 것이다.

import java.util.*;

class Process implements Comparable<Process> {
    int priority;
    int idx;

    public Process(int priority, int idx) {
        this.priority = priority;
        this.idx = idx;
    }

    public int compareTo(Process p) {
        if(this.priority == p.priority) return this.idx - p.idx;
        else return p.priority - this.priority;
    }
}
class Solution {
    public int solution(int[] priorities, int location) {
        PriorityQueue<Process> pq = new PriorityQueue<>();

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

        int answer = 1;
        while(!pq.isEmpty()) {
            Process cur = pq.poll();

            if(cur.idx == location) break;
            else answer++;
        }

        return answer;
    }
}

60점. 절반 정도는 맞았다. 하지만 이 접근은 문제의 핵심을 놓친 것이었다.

이 문제는 단순히 높은 우선순위부터 전역적으로 꺼내는 구조가 아니다. 동작 방식을 다시 읽으면, 큐의 맨 앞 프로세스를 꺼낸 뒤 현재 큐에 자신보다 우선순위가 높은 것이 있으면 다시 뒤로 보낸다. 없을 때만 실행된다. 즉 원래 순서(큐의 앞뒤 관계)를 유지하면서, 맨 앞 원소가 기준이 되어 조건부로 실행 여부를 판단하는 시뮬레이션이다. PriorityQueue는 전체를 우선순위 기준으로 정렬해서 꺼내는 자료구조라, 이 흐름을 재현할 수 없다.

---

중간 3번의 북벌

우선순위 큐로는 안 된다는 걸 느끼고 일반 덱으로 방향을 틀었다. 매 라운드마다 덱 전체를 순회해 최대 우선순위를 파악하고, 해당 원소를 꺼내는 구조를 짰다. 4트까지 이 방향으로 이것저것 고쳐봤는데, 계속 엣지 케이스에서 틀렸다. 60점 벽을 넘지 못했다.

나중에 돌아보니 이유가 명확했다. 덱에서 전체 최대값을 찾아 바로 꺼내면, 큐 순서가 사라진다. 예를 들어 [1, 1, 9, 1, 1]에서 location = 0이라면, 맨 앞의 1은 9보다 우선순위가 낮아 뒤로 밀려야 하고, 9가 실행된 뒤 남은 1들이 원래 순서대로 실행되어야 한다. 그런데 내 코드는 그냥 9를 전체에서 꺼내버리니, 그 이후의 순서 보장이 깨졌다. "전체 최대를 찾는다"와 "맨 앞 원소가 기준이다"를 계속 혼동하고 있었던 것이다.

---

5트 (정답)

3시간을 넘기고 나서 싱싱했던 반년 전 나의 정답 코드를 참고했다. 보는 순간 바로 이해가 됐다.

import java.util.*;

class Process {
    int index;
    int priority;

    public Process(int index, int priority) {
        this.index = index;
        this.priority = priority;
    }
}

class Solution {
    public int solution(int[] priorities, int location) {
        Queue<Process> q = new LinkedList<>();

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

        int answer = 1;
        while(true) {
            int max = 0;
            for(int i=0; i<q.size(); i++) {
                Process tmp = q.poll();
                max = Math.max(max, tmp.priority);
                q.offer(tmp);
            }

            while(true) {
                Process tmp = q.peek();
                if(tmp.priority == max) break;
                else q.offer(q.poll());
            }
            Process cur = q.poll();
            if(cur.index == location) break;
            else answer++;
        }

        return answer;
    }
}

구조는 두 단계다. 먼저 현재 큐 전체를 순회해 최대 우선순위 max를 구한다. 그 다음 큐의 맨 앞부터 확인하며, max와 우선순위가 같은 원소가 나올 때까지 뒤로 보낸다. 맨 앞에 온 순간 꺼내서 실행한다.

내가 계속 놓쳤던 건 이 두 번째 단계였다. 최대값을 찾은 뒤 바로 꺼내는 게 아니라, 큐 순서를 보존하면서 해당 원소가 맨 앞에 올 때까지 기다렸다가 꺼낸다. 이렇게 해야 "대기 중인 프로세스 중 우선순위가 높은 것이 있으면 먼저 처리"한다는 조건이 순서까지 포함해서 정확히 재현된다.

---

나의 사투가 보이는가... 3시간 동안 헤맨 이유를 한 마디로 정리하면, "맨 앞 원소가 기준"이라는 걸 끝까지 이해하지 못했다. 문제 설명을 읽고 우선순위가 높은 것부터 처리한다는 부분만 보고 우선순위 큐로 먼저 달려들었고, 방향을 바꾼 뒤에도 "전체에서 최대를 찾아 꺼낸다"는 사고에서 벗어나지 못했다. 큐 자료구조의 핵심은 순서인데, 그 순서를 시뮬레이션의 도구로 써야 한다는 감각이 부족했다. 과거의 코드를 참고했다는 게 조금 부끄럽지만, 덕분에 내가 어디서 막혔는지는 명확하게 정리됐다.