스텍 / 큐 : 프로세스

문제 이해

• 여러 문서들이 프린터 대기열에 있음
• 각 문서마다 중요도가 있다 (숫자가 클수록 중요)
• 프린터 규칙: 현재 문서보다 중요한 문서가 뒤에 있으면, 현재 문서를 맨 뒤로 보내고 중요한 문서를 먼저 인쇄
• 특정 문서가 몇 번째로 인쇄되는지 구하기

핵심 아이디어

각 문서에 **[중요도, 고유번호]**를 저장하여 큐에서 순서 추적하고, 프린터의 실제 동작을 시뮬레이션한다.

접근 방법

1. 문서 추적: [중요도, 원래 인덱스] 형태로 큐에 저장
2. 큐 활용: FIFO 특성으로 프린터 대기열 구현
3. 우선순위 체크: 현재 문서보다 중요한 문서가 뒤에 있는지 확인
4. 시뮬레이션: 인쇄 또는 대기열 맨 뒤로 이동 결정

코드

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        // 1. 큐에 [중요도, 고유번호] 형태로 저장
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < priorities.length; i++) {
            queue.offer(new int[]{priorities[i], i});
        }
        
        int printOrder = 0;  // 인쇄 순서
        
        // 2. 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            int[] current = queue.poll();  // 맨 앞 문서
            int currentPriority = current[0];
            int currentId = current[1];
            
            // 3. 현재 문서보다 중요한 문서가 뒤에 있는지 확인
            boolean hasHigherPriority = false;
            for (int[] process : queue) {
                if (process[0] > currentPriority) {
                    hasHigherPriority = true;
                    break;
                }
            }
            
            // 4. 더 중요한 문서가 있으면 뒤로 보내기
            if (hasHigherPriority) {
                queue.offer(current);
            } else {
                // 5. 인쇄! 순서 증가
                printOrder++;
                
                // 6. 내가 찾던 문서면 순서 반환
                if (currentId == location) {
                    return printOrder;
                }
            }
        }
        
        return -1;  // 이론상 여기 올 일 없음
    }
}

핵심 포인트

• int[] 배열: [중요도, 고유번호]로 문서 정보 추적
• for-each 문: 큐의 모든 요소를 순차적으로 확인
• break 활용: 더 중요한 문서 하나만 찾으면 즉시 중단
• 실제 프린터 동작: 한 번에 하나씩 처리하며 우선순위 검사

시간복잡도

O(N²) - N은 문서 수, 최악의 경우 각 문서마다 모든 대기 문서를 확인