알고리즘 스터디 2주차 - 2

이강민·2024년 7월 28일

Kernel360 알고리즘

커널360

목록 보기

14/56

1966

알고리즘 : 큐
난이도 : 실버3

문제

1966

접근

중요도에 따라 문서를 출력한다.
문서의 순서는 0부터 시작한다.
- 인덱스를 적용해야한다? --> 배열
문서는 중요도로만 적혀있다.
- 큐를 이용하는데 중요도로 출력한다? --> 우선순위 큐?

가정

배열과 우선순위 큐로 풀 수 있다.
출력해야 하는 문서를 저장한다.
처음 주어진 문서의 순서는 정해져 있고 적혀있는 숫자는 우선순위다.
- 문서의 순서, 우선순위를 저장한다.
우선순위에 따라 출력할 때 출력해서 받아야하는 문서가 몇번째로 출력되는지 결과를 리턴한다.

풀어보기

package org.example;

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        StringBuilder sb = new StringBuilder();
        //1사이클
        // 문서 갯수, 출력해야 하는 문서
        // 문서들이 있다.
        for(int i = 0; i < N; i++){
            String[] doc = reader.readLine().split(" ");
            int printDocIndex = Integer.parseInt(doc[1]);
            String[] priorities = reader.readLine().split(" ");


            Queue<Document> queue = new LinkedList<>();
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

            for(int j = 0; j<priorities.length; j++){
                int priority = Integer.parseInt(priorities[j]);
                //큐에 담는다.
                queue.add(new Document(j, priority));
                priorityQueue.add(priority);
            }
            int count = 0;
            while(!queue.isEmpty()){
                Document current = queue.poll();
                if (current.priority == priorityQueue.peek()) {
                    priorityQueue.poll();
                    count++;
                    if (current.index == printDocIndex) {
                        sb.append(count).append("\n");
                        break;
                    }
                } else {
                    queue.add(current);
                }
            }
        }
        System.out.println(sb.toString());

    }
}
class Document{
    final int index;
    final int priority;

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

시행착오

단순 priorityQueue로 해결하려고 했다.
- 운선순위 큐를 그대로 사용할 경우 같은 우선순위를 가진 값에 대해 마지막에 입력 받은 값이 더 우선순위가 높아져 출력 시 순서가 뒤로 밀리는 경우가 발생했다.
  - 반례 :
```
 1  
 9 0
 1 1 9 1 1 9 6 7 8
  # 결과 : 8
  # 정답 : 6
```
일반 큐와 우선순위 큐로 중복되는 우선순위를 핸들링해야한다.

Queue<Document> queue = new LinkedList<>();
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

우선순위 큐와 일반 큐를 2개 준비한다.

for(int j = 0; j<priorities.length; j++){
     int priority = Integer.parseInt(priorities[j]);
     queue.add(new Document(j, priority));
     priorityQueue.add(priority);
}

각각 일반 큐에는 우선순위와 인덱스 값을, 우선순위 큐에는 우선순위 값을 담는다.

while(!queue.isEmpty()){
   Document current = queue.poll();
   if (current.priority == priorityQueue.peek()) {
      priorityQueue.poll();
      count++;
      if (current.index == printDocIndex) {
         sb.append(count).append("\n");
         break;
      }
 } else {
     queue.add(current);
   }
 }