[220817][BC][인프런](9-4) 최대 수입 스케쥴

[honeySleepr]

📌 문제

• 문제

⭐️ 아이디어

• 수입이 가장 중요하니까 최대 수입 부터 내림차순으로 정렬하고, 수입이 같을 때는 기한이 긴 것 순으로 정렬한다
• 강연 날짜를 Key, 수입을 Value로 하는 Map을 만든다.
• 가장 수입이 큰 것 부터, 가능한한 마지막 날의 Map에 넣는다. (ex: 기한이 5이면 Key를 5로 하는 Map에 넣는다)
• 해당 날짜에 이미 강연이 있으면, day-- 날짜를 하루씩 당기면서 넣을 수 있는 곳에 넣는다
• 넣을 수 있는 강연을 모두 넣었으면 Map안에 들어간 각 수입료들을 합한 값이 답이다.

🤔 고민한 내용

• 수입료가 우선인가, 남은 기한이 우선인가?

💪 새롭게 배운 내용

• PriorityQueue를 배웠다

🆘 이해가 어려운 내용

❌ 해결하지 못한 이유

✅ 본인 풀이

🏋️‍♀️ 시도횟수 : n회 | ⏱ 걸린시간 : 100ms | 💾 메모리 : 100MB

• Map 활용 풀이

  public class P0904 {
  
  public static void main(String[] args) throws IOException {
               ...
      // int n = 강연 수
      // List<Lecture> lectures = 강연들을 넣은 리스트
      int answer = 0;
      Collections.sort(lectures); // compareTo 오버라이딩 하여 수입 기준으로 내림차순 정렬, 수입이 같을 경우 기한으로 내림차순
      for (Lecture l : lectures) {
          int date = l.dDay;
  
          while (date > 0) {
                               /* 해당 날짜가 비어있으면 일정 추가 */
              if (!map.containsKey(date)) {
                  map.put(date, l.pay);
                  answer += l.pay;
                  break;
              }
              date--;
          }
      }
      System.out.println(answer);
  }
  
  static class Lecture implements Comparable<Lecture> {
  
      private int pay;
      private int dDay;
  
      public Lecture(int pay, int dDay) {
          this.pay = pay;
          this.dDay = dDay;
      }
  
      @Override
      public int compareTo(Lecture o) {
          if (this.pay == o.pay) {
              return -(this.dDay - o.dDay); // 내림 차순
          }
          return -(this.pay - o.pay); // 내림 차순
      }
  }
  }

• PriorityQueue 활용 풀이 ( Collections.sort(lectures) 까지, 그리고 Lecture 클래스 생성 부분은 위와 동일)

      int date = lectures.get(0).dDay;
      int index = 0;
      while (date > 0) {
          while (index < lectures.size() && lectures.get(index).dDay == date) {
              pQueue.add(lectures.get(index).pay);
              index++;
          }
          if (pQueue.size() > 0) {
              answer += pQueue.poll();
          }
          date--;
      }
  
      System.out.println(answer);