[Algorithm: 큐] 프로그래머스 <프로세스>

스택/큐 Java Programmers Lv.2

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42587?language=java

프로그래머스

 

---

 

문제 설명

실행 대기 큐에서 프로세스를 꺼낼 때, 큐에 우선순위가 더 높은 프로세스가 남아 있다면 다시 큐에 넣는다. 그렇지 않으면 실행한다. 특정 프로세스(location)가 몇 번째로 실행되는지 구하는 문제다.

priorities	location	return
[2, 1, 3, 2]	2	1
[1, 1, 9, 1, 1, 1]	0	5

[2, 1, 3, 2] → C(우선순위 3)가 가장 높으므로 먼저 실행
실행 순서: C → D → A → B
location=2 (C)는 1번째로 실행

 

 

---

 

핵심 아이디어

이 문제의 가장 큰 어려움은 "내가 찾는 프로세스가 어디 있는지"를 추적하는 것이다. 큐에서 꺼내고 다시 넣는 과정이 반복되면 위치가 계속 바뀌기 때문이다.

해결법: 큐에 {index, priority} 쌍으로 넣는다.
원래 인덱스를 값과 함께 보관하면, 몇 번이나 순환해도
current[0] == location으로 내가 찾는 프로세스인지 확인할 수 있다.

초기 큐 상태 — {index, priority} 쌍으로 저장

큐(앞→뒤)

A{0, 2}

B{1, 1}

C{2, 3}

D{3, 2}

location=2 → index가 2인 C를 찾아야 함 (주황색 표시)

 

예시 1: [2, 1, 3, 2], location=2

Step 1 — A{0,2} poll → 큐에 더 높은 우선순위(3) 존재

poll

A{0, 2}poll

│

B{1, 1}

C{2, 3}

D{3, 2}

큐 안에 C(우선순위 3) > A(우선순위 2) → 다시 뒤에 넣기

offer 후

B{1, 1}

C{2, 3}

D{3, 2}

A{0, 2}뒤로

다시 큐 뒤로 → answer 변화 없음

Step 2 — B{1,1} poll → 큐에 더 높은 우선순위 존재

poll

B{1, 1}poll

│

C{2, 3}

D{3, 2}

A{0, 2}

큐 안에 C(3) > B(1) → 다시 뒤에 넣기

offer 후

C{2, 3}

D{3, 2}

A{0, 2}

B{1, 1}뒤로

다시 큐 뒤로 → answer 변화 없음

Step 3 — C{2,3} poll → 큐에 더 높은 우선순위 없음 → 실행!

poll

C{2, 3}poll

│

D{3, 2}

A{0, 2}

B{1, 1}

남은 큐 최대 우선순위 = 2 < C(3) → 실행. answer++ → answer=1

current[0]=2 == location=2 → 정답 발견!

answer = 1 반환

예시 2: [1, 1, 9, 1, 1, 1], location=0

A(index=0, priority=1)를 찾아야 한다. C(priority=9)가 압도적으로 높아서 A~F 중 C가 먼저 실행된다.

초기 큐 — location=0, 즉 A{0,1}를 추적

초기

A{0, 1}

B{1, 1}

C{2, 9}

D{3, 1}

E{4, 1}

F{5, 1}

C(9)가 있는 한 A, B, D, E, F는 계속 뒤로 밀린다

C 실행 후 순서 — answer=1

C 실행

C실행1번째

│

D{3, 1}

E{4, 1}

F{5, 1}

A{0, 1}

B{1, 1}

이후 D(2번째) → E(3번째) → F(4번째) → A(5번째) 순서로 실행

A의 current[0]=0 == location=0 → answer=5 반환

answer = 5 반환

 

 

---

 

설계 포인트

왜 {index, priority} 쌍으로 넣는가?

우선순위만 큐에 넣으면 프로세스가 큐를 순환하는 동안 내가 찾는 프로세스가 어디 있는지 알 수 없다. 원래 인덱스를 함께 보관해야 어떤 상황에서도 추적이 가능하다.

우선순위가 같은 프로세스가 여러 개일 때 특히 중요하다.
예시 2에서 A, B, D, E, F는 모두 우선순위가 1로 같다.
index 없이는 A가 실행됐는지 B가 실행됐는지 구분할 수 없다.

우선순위 비교 방법

현재 꺼낸 프로세스보다 높은 우선순위가 큐에 있는지 확인할 때, 큐 전체를 순회하며 단 하나라도 발견하면 즉시 break한다.

for (int[] arr : queue) {
    if (current[1] < arr[1]) {  // 현재보다 높은 우선순위 발견
        isHigher = true;
        break;               // 하나만 있어도 충분 → 즉시 종료
    }
}

Java의 ArrayDeque는 for-each로 순회가 가능하다.
poll/offer와 함께 내부 원소를 조회하는 이 방식이 이 문제에서 자연스럽게 동작한다.

 

전체 흐름 정리

1

모든 프로세스를 {index, priority} 쌍으로 큐에 넣는다

2

큐에서 하나를 poll()한다

3

남은 큐를 순회해 현재보다 높은 우선순위가 있으면 다시 offer()

4

없으면 실행: answer++, current[0] == location이면 반환

 

 

---

 

최종 코드

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        Queue<int[]> queue = new ArrayDeque<>();

        // {원래 인덱스, 우선순위} 쌍으로 큐에 삽입
        for (int i = 0; i < priorities.length; i++) {
            queue.offer(new int[]{i, priorities[i]});
        }

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            boolean isHigher = false;

            // 현재보다 우선순위 높은 프로세스가 큐에 있는지 확인
            for (int[] arr : queue) {
                if (current[1] < arr[1]) {
                    isHigher = true;
                    break;
                }
            }

            if (isHigher) {
                queue.offer(current);    // 다시 뒤에 넣기
            } else {
                answer++;                // 실행 순서 카운트
                if (current[0] == location) {
                    return answer;   // 찾는 프로세스 실행 → 반환
                }
            }
        }
        return answer;
    }
}

 

 

 

---

 

 

정리

{index, priority} 쌍

큐 순환 중에도 원래 인덱스를 보존. 우선순위가 같은 프로세스가 여러 개여도 정확히 추적 가능.

큐 순환 시뮬레이션

poll → 비교 → offer(뒤로) 또는 실행. 문제의 규칙을 코드로 그대로 옮긴 구조.

즉시 반환

target 프로세스가 실행되는 순간 answer를 반환. 이후 다른 프로세스를 더 탐색할 필요 없음.

for-each on Queue

ArrayDeque는 for-each 순회 가능. 

"어떻게 효율적으로 찾느냐"보다 "내가 찾는 대상을 어떻게 식별하느냐"가 핵심
index를 함께 보관하는 패턴은 큐/스택 시뮬레이션 문제 패턴을 파악하자. 

 

 

 

* 이 포스팅은 Claude AI의 도움을 받아서 작성되었습니다.