인프런 최대수입스케쥴

문제

나의 풀이

import java.util.*;

public class LectureSchedule {
    static 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 o) {
            return o.time - this.time; // 날짜를 기준으로 내림차순 정렬
        }
    }

    static int n, max = Integer.MIN_VALUE;
    public static 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--) { // 입력 박은 가장 큰 날짜부터 하루씩 작아져서 1일까지 반복
            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) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        ArrayList<Lecture> arr = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            int m = sc.nextInt();
            int d = sc.nextInt();
            arr.add(new Lecture(m, d));
            if(d > max) {
                max = d; // 가장 큰 날짜 구해주기
            }
        }
        System.out.println(LectureSchedule.solution(arr));
    }
}

입력 받을 때 가장 큰 날짜를 max에 저장시키고나서 시간에 대해서 내림차순 정렬을 시킨다.
그런 다음 max 날짜에서부터 날짜가 감소하는 순으로 탐색한다. 탐색을 하면서 현재 날짜와 같은 기한인 강연들만 우선순위큐에 넣어주고 강연 마감 날짜가 현재 날짜보다 작아지면 멈춰서 우선순위 큐에서 원소를 꺼내주어 값을 answer에 더해준다. 그렇게 되면 해당 날짜에 가장 많은 강연료를 받을 수 있는 강연을 선택하게 되는 것이다. 그 다음 현재 탐색 날짜를 1 감소시켜서 다시 탐색해주주며, 이 과정을 날짜가 끝날때까지 반복해준다.

결과

인프런 꽃이 피는 최단시간

문제

나의 풀이

import java.util.Arrays;

public class FloweringTime {
    public static int solution(int[] plantTime, int[] growTime) {
        int answer = 0;
        int n = plantTime.length;
        int list[][] = new int[n][2];
        for(int i = 0; i < n; i++) {
            list[i][0] = plantTime[i];
            list[i][1] = growTime[i];
        }
        Arrays.sort(list, (a, b) -> b[1] - a[1]); // 성장기간 기준 내림차순 정렬(성장기간이 긴걸 먼저 심는 게 최단시간을 구할 수 있음)
        int start = 0, end = 0;
        for(int[] x : list) {
            end = start + x[0] + x[1]; // x 꽃까지 피는 데 걸리는 시간
            answer = Math.max(answer, end); // 모든 꽃이 피는 데 걸리는 최단 시간을 구하기 위해 업데이트
            start += x[0]; // 다음번째가 시작되는 시점을 위해 x꽃 심는데 걸리는 시간 더해주기
        }
        return answer;
    }
    public static void main(String[] args) {
        System.out.println(FloweringTime.solution(new int[]{2, 1, 4, 3}, new int[]{2, 5, 3, 1}));
    }
}

plantTime 배열 원소의 합은 무조건 걸리는 시간이다. 그렇기 때문에, 이 기간이 지난 바로 다음 마지막 꽃이 피는 기간을 가장 짧게 만들어야 최단시간을 만들 수 있다. 즉, 성장 기간인 growTime이 긴것을 먼저 심고 짧은 것을 나중에 심도록 구현하면 된다.
심는기간과 성장기간을 하나로 묶어서 2차원 배열 list로 만들어준다. 그런 다음 성장 기간에 대해서 내림차순 정렬을 해준다. list에 대해서 i로 반복문을 도는데 하나의 원소를 탐색할 때 end 변수를 start + 현재꽃의 심는 기간 + 현재꽃의 성장기간 의 합으로 업데이트해주고 answer값이 end값 보다 작은 경우 end값으로 업데이트 해주어 i번째 꽃까지 피는데 걸리는 시간을 answer로 나타낸다. 다음 번째 원소로 가기전에는 start 값에 i번째 꽃을 심는 기간을 더해주어야 다음 번째 꽃을 언제 심을수 있는지 알 수 있다.
반복문을 다 돌고나면 answer를 리턴해주면 된다.

결과