[문제풀이] 09-04. 최대 수입 스케줄

인프런, 자바(Java) 알고리즘 문제풀이

Greedy Alogorithm - 0904. 최대 수입 스케쥴(우선순위큐)

---

🗒️ 문제

---

🎈 나의 풀이

	private static class Lecture implements Comparable<Lecture> {
        int pay, day;

        public Lecture(int pay, int day) {
            this.pay = pay;
            this.day = day;
        }

        @Override
        public int compareTo(Lecture o) {
            if(this.pay == o.pay) return this.day - o.day;
            return o.pay - this.pay;
        }
    }
    private static int solution(List<Lecture> list) {
        int pay = 0;
        Map<Integer, Integer> schedule = new HashMap<>();
        Collections.sort(list);

        for(Lecture l : list) {
            for(int i=l.day; i>0; i--) {
                if(!schedule.containsKey(i)) {
                    schedule.put(i, i);
                    pay += l.pay;
                    break;
                }
            }
        }

        return pay;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Lecture> list = new ArrayList<>();

        for(int i=0; i<n; i++) list.add(new Lecture(sc.nextInt(), sc.nextInt()));

        System.out.println(solution(list));
    }

---

🖍️ 강의 풀이

  class Lecture implements Comparable<Lecture>{
      public int money;
      public int time;
      Lecture(int money, int time) {
          this.money = money;
          this.time = time;
      }
      @Override
      public int compareTo(Lecture ob){
          return ob.time-this.time;
      }
  }

  class Main {
      static int n, max=Integer.MIN_VALUE;
      public int solution(ArrayList<Lecture> arr){
          int answer=0;
          PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
          Collections.sort(arr);
          int j=0;
          for(int i=max; i>=1; i--){
              for(; j<n; j++){
                  if(arr.get(j).time<i) break;
                  pQ.offer(arr.get(j).money);
              }
              if(!pQ.isEmpty()) answer+=pQ.poll();
          }
          return answer;
      }

      public static void main(String[] args){
          Main T = new Main();
          Scanner kb = new Scanner(System.in);
          n=kb.nextInt();
          ArrayList<Lecture> arr = new ArrayList<>();
          for(int i=0; i<n; i++){
              int m=kb.nextInt();
              int d=kb.nextInt();
              arr.add(new Lecture(m, d));
              if(d>max) max=d;
          }
          System.out.println(T.solution(arr));
      }
  }

---

💬 짚어가기

해당 문제는 Priority Queue를 이용하여 풀 수 있다. 나의 풀이에서는 우선순위큐를 접하기
이전에 풀이한 방식으로 구현해 보았다.

우선 강연의 강연료와 기한을 보관할 수 있는 클래스를 생성하고, 비용이 크고 기한이 긴 순서대로
강연을 정렬할 수 있도록 하였다.

이후 정렬된 강연 요청 리스트를 순회하며 비용이 가장 큰 강연부터 Map에 보관하도록 하였는데,
기한을 key로하여 해당 기한에 강연이 존재하는지 판별하도록 하여 문제를 해결했다.

Priority Queue로 풀기
강의에서는 강연을 기한을 기준으로 역순(기한이 긴 강연이 앞에 오도록)이 되도록 정렬하였다.
전체에서 가장 긴 기한을 기준으로, 기한이 일치하는 강연들의 강연료를 Priority Queue에
집어 넣고, poll()을 수행하며 제일 비싼 강연료를 뽑는다.

이렇게 기준 기한을 하루씩 줄여가며 Priority Queue에 강연료를 추가로 넣고, 기한이 1일이
되는 때 까지 반복 수행하여 최대 수입을 얻는다.