boj13904 과제_java

문제

웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

입력

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

나의 풀이

• 내가 가능한 범위에서 for문을 돌면서 내 현재 score보다 작은 값이있으면 갱신해주고, 최종적으로 합을 출력하는 방법으로 해결하였다.

Guide to Java 8 Comparator.comparing() | Baeldung

• 핵심 코드

  for (int i = 0; i < hws.size(); i++) {
              Hw now = hws.get(i);
  
              if(orders[now.getDay()-1]==0) orders[now.getDay()-1]=now.getScore();
              else {
                  int minIndex = 0;
                  int min = orders[0];
                  for (int j = 1; j < now.getDay(); j++) {
                      if(min>orders[j]){
                          min = orders[j];
                          minIndex = j;
                      }
                  }
                  if(min<now.getScore()){
                      orders[minIndex] = now.getScore();
                  }
              }
  
          }

• 전체 코드

  package Baekjoon.java.gold;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.*;
  import java.util.stream.Collectors;
  
  //과제
  public class boj13904 {
  
      private static class Hw{
          int day;
          int score;
  
          public Hw(int day, int score) {
              this.day = day;
              this.score = score;
          }
  
          public int getDay() {
              return day;
          }
  
          public int getScore() {
              return score;
          }
      }
  
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  
          int N = Integer.parseInt(br.readLine());
          int finish = 0;
          List<Hw> hws = new ArrayList<>();
  
          for (int i = 0; i < N; i++) {
              StringTokenizer st = new StringTokenizer(br.readLine());
              int day = Integer.parseInt(st.nextToken());
              int score = Integer.parseInt(st.nextToken());
              if(day>finish) finish = day;
              Hw hw = new Hw(day,score);
              hws.add(hw);
          }
  
          int[] orders = new int[finish];
          Arrays.fill(orders,0);
          hws = hws.stream().sorted(Comparator.comparing(Hw::getDay).thenComparing(Hw::getScore)).collect(Collectors.toList());
  
          for (int i = 0; i < hws.size(); i++) {
              Hw now = hws.get(i);
  
              if(orders[now.getDay()-1]==0) orders[now.getDay()-1]=now.getScore();
              else {
                  int minIndex = 0;
                  int min = orders[0];
                  for (int j = 1; j < now.getDay(); j++) {
                      if(min>orders[j]){
                          min = orders[j];
                          minIndex = j;
                      }
                  }
                  if(min<now.getScore()){
                      orders[minIndex] = now.getScore();
                  }
              }
  
          }
  
          System.out.println(Arrays.stream(orders).sum());
      
      }
  }

결과