[백준 PriorityQueue] 13904번: 과제 (Java)

https://www.acmicpc.net/problem/13904

 

 

우선순위 큐를 사용하지 않았을 때 (2중 for문)

N (1 ≤ N ≤ 1,000) 범위로 주어졌기 때문에 2중 for문도 통과된다. (N의 범위가 1만까지는 2중 for문을 허용해도 된다)

import java.util.*;
import java.io.*;
  
public class Main {
  static int n;
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      n = Integer.parseInt(br.readLine());
      
      List<Assignment> list = new ArrayList<>();
      
      int finalDate = 0;
      for (int i = 0; i < n; i++) {
          String[] input = br.readLine().split(" ");
          int dueDate = Integer.parseInt(input[0]);
          int score = Integer.parseInt(input[1]);
          
          finalDate = Math.max(finalDate, dueDate);
          list.add(new Assignment(dueDate, score));
      }
      
      Collections.sort(list, (a, b) -> b.score - a.score);
      
      int[] scores = new int[finalDate + 1];
      
      // 이중 for문으로 해결
      for (Assignment a : list) {
          for (int i = a.dueDate; i > 0; i--) {
              if (scores[i] == 0) {
                  scores[i] = a.score;
                  break; 
              }
          }
      }
      
      
      int sum = 0;
      for (int m : scores) sum += m;
      System.out.println(sum);
      
  }
    static class Assignment {
        int dueDate;
        int score;

        Assignment (int dueDate, int score) {
            this.dueDate = dueDate;
            this.score = score;
        }
    }
}

 

 

 

import java.util.*;
import java.io.*;
  
public class Main {
  static int n;
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      n = Integer.parseInt(br.readLine());
      
      int finalDate = 0;
      List<Assignment> list = new ArrayList<>();
      
      // 가장 작은 점수가 나오는 우선순위 큐
      PriorityQueue<Integer> pq = new PriorityQueue<>();
      
      for (int i = 0; i < n; i++) {
          String[] input = br.readLine().split(" ");
          int dueDate = Integer.parseInt(input[0]);
          int score = Integer.parseInt(input[1]);
          
          finalDate = Math.max(finalDate, dueDate);
          list.add(new Assignment(dueDate, score));
      }
      
      // 마감일 오름차순 리스트 정렬
      Collections.sort(list, (a, b) -> a.dueDate - b.dueDate); 
      
      for (Assignment a : list) {
          pq.offer(a.score);
          
          if (pq.size() > a.dueDate) pq.poll();
      }
      
      int sum = 0;
      while (!pq.isEmpty()) {
          sum += pq.poll();
      }
      
      System.out.println(sum);
      
  }
    static class Assignment {
        int dueDate;
        int score;

        Assignment (int dueDate, int score) {
            this.dueDate = dueDate;
            this.score = score;
        }
    }
}

 

우선순위 큐는 for each 순회가 되지 않는다. (내부적으로 heap 자료구조를 사용하기 때문)

 

 

for (Assignment a : list) {
          pq.offer(a.score);
          if (pq.size() > a.dueDate) pq.poll();

}

 

ArrayList : 과제를 마감일이 빠른 것부터 정렬하여 담아둔다. (1일, 2일, 4일 ...)

PriorityQueue : 마감일이 빠른 순으로 과제들의 점수를 하나씩 담아둔다. (1일의 점수, 2일의 점수, 4일의 점수 ..)

 

if (pq.size() > a.dueDate) pq.poll();

과제의 마감일보다 우선순위 큐의 크기가 클 경우 pq.poll() -> 점수가 작은 수가 poll된다. (오름차 우선순위)