[220816][반스][인프런](9-4) 최대 수입 스케줄

[ffinn92]

📌 문제

• 문제

⭐️ 아이디어

• 먼저 (x, y)에서 y(작업기간)으로 내림차순 정렬 한다.

• PriorityQueue를 Collections.reverseOrder() 활용하여 내림차순 정렬로 초기화한다.

• number에 가장 긴 강연기간을 넣어줘서 초기화해준다.

• for문을 통해 현재 강연과 이전 강연(number)의 기간이 같다면 ( 60, 3 ) 과 ( 30, 3 ) 이전의 강연료를 PriorityQueue에 넣어준다.

• 넣어준 뒤, 이전 강연(number) 기간을 현재 강연기간으로 갱신해준다. <- 이건 해줄필요 없었네..?

• 만약 기간이 다르다면 ( 30, 3 ) ( 50, 2 ) PriorityQueue에서 poll하여 가장 큰수를 뽑는다.

• 뽑은수는 answer에 더해준다.

• PriorityQueue에 현재 기간의 강연료를 넣어준다(여기서는 50)

• number를 현재 강연기간으로 갱신한다.( 3 -> 2 )

• 반복한다.

🤔 고민한 내용

• 기간이 마지막에 1이 여러개일때는 어떻게 하지? 내 로직에서는 같을때 계속 넣기만하는데..! 아 마지막에 한번 poll()해서 남은것중에 가장큰 수를 넣으면되겠다.(응 아니야~)

💪 새롭게 배운 내용

• PriorityQueue에 대해 배웠고, 꼭 이중 for문을 절대적으로 피할필요는 없구나 ㅠ break를 쓰니까

🆘 이해가 어려운 내용

• for문에서 i for문은 감소하고 j for문은 증가하면서 정렬된 인덱스를 찾아가는 개념이 이해하기 어려웠다.

❌ 해결하지 못한 이유

• 이중 for문 활용못한것, 예외의 경우 생각 못한것

✅ 본인 풀이

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

import java.util.*;

class Lecture implements Comparable<Lecture> {
    public int income;
    public int days;

    public Lecture(int income, int days) {
        this.income = income;
        this.days = days;
    }
    @Override
    public int compareTo(Lecture ob) {
        return ob.days - this.days;
    }
}

public class If904MaxIncome {
    public int solution (ArrayList<Lecture> arr) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        Collections.sort(arr);
        int number = 0;
        number = arr.get(0).days;

        for (Lecture lecture : arr) {
            if(lecture.days == number) {
                pq.offer(lecture.income);
                number = lecture.days;
            }else {
                Integer maxIncome = pq.poll();
                answer += maxIncome;
                pq.offer(lecture.income);
                number = lecture.days;
            }
        }

        Integer lastMaxIncome = pq.poll();
        answer += lastMaxIncome;

        return answer;
    }

    public static void main(String[] args) {
        If904MaxIncome T = new If904MaxIncome();
        Scanner sc = new Scanner(System.in);

        int lecturs = sc.nextInt();
        ArrayList<Lecture> arr = new ArrayList<>();
        for (int i = 0; i < lecturs; i++) {
            int income = sc.nextInt();
            int days = sc.nextInt();
            arr.add(new Lecture(income, days));
        }

        System.out.println(T.solution(arr));
    }

}

참고한 자료

• 링크