[백준] 1966번: 프린터 큐

💡문제 분석 요약

프린터 대기열에서 문서의 중요도에 따라 인쇄 순서가 정해지는 프린터에서, 주어진 타켓 문서가 몇 번째로 인쇄되는지 출력하는 문제이다.

• 시간 제한: 2초
• 메모리 제한: 128MB

 

💡알고리즘 설계

• `Queue<int[]>` 를 사용해 각 문서의 위치(인덱스)와 중요도를 저장한다.
• 큐가 빌 때까지
  • 큐의 첫 번째 문서를 poll
  • 뒷 순서의 문서들과 중요도를 비교하여
    • 더 높은 중요도의 문서가 존재하면 첫 번째 문서를 맨 뒤로 이동 (출력X)
    • ~ 존재하지 않으면 출력 개수 증가(출력O) & 타겟 문서인지 확인

 

💡코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int test = Integer.parseInt(br.readLine());

        Queue<int[]> q = new LinkedList<>();

        while(test-- > 0) {
            q.clear();
            int count = 0;
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++) {
                int[] a = {i, Integer.parseInt(st.nextToken())};
                q.offer(a); // {index, priority}
            }

            while(!q.isEmpty()) {
                int[] first = q.poll();
                boolean pass = true;
                for(int[] doc : q) {
                    if(first[1] < doc[1]){
                        q.offer(first);
                        pass = false; break;
                    }
                }
                if(pass) {
                    count++;
                    if(m == first[0]) break;
                }
            }

            sb.append(count).append("\\n");
        }

        System.out.println(sb);
        br.close();
    }
}

 

💡시간복잡도

O(N²)

 

💡 틀린 이유

count 변수를 각 테스트 케이스마다 0으로 초기화하지 않았다.

 

💡 다른 풀이

처음에는 ‘중요도’라는 단어를 보고 우선순위 큐를 생각했지만, 중요도 순으로만 출력하는 것이 아니라 재배치하는 과정이 필요했기 때문에 일반 큐만 사용하여 구현했다.

 

💡 느낀점 or 기억할정보

Queue에 int[]을 타입으로 사용해서 문서의 위치와 중요도를 한 요소로 정의하는 것이 유용했다.