[BaekJoon] 17420 깊콘이 흘러넘쳐 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/17420

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int giftCardNum;
    static PriorityQueue<GiftCard> giftCards;

    static void input() {
        Reader scanner = new Reader();

        giftCardNum = scanner.nextInt();

        List<GiftCard> giftCardList = new ArrayList<>();

        for(int idx = 0; idx < giftCardNum; idx++) {
            giftCardList.add(new GiftCard(scanner.nextInt(), 0));
        }

        for(int idx = 0; idx < giftCardNum; idx++) {
            giftCardList.get(idx).plan = scanner.nextInt();
        }

        giftCards = new PriorityQueue<>(giftCardList);
    }

    /*
        1. 주어진 기프티콘을 사용할 계획에 따라 오름차순으로, 같다면 기한 기준 오름차순으로 정렬한다
        2. 각 기프티콘에 대해 연장해야 할 횟수를 구하여 이를 누적한다
            - 기프티콘은 사용할 계획에 해당하는 일수에만 사용할 수 있기 때문에 이에 맞춰서 사용 기한을 연장해줘야 한다
                - 즉, 사용할 계획이 같은 기프티콘끼리는 사용 기한에 제약이 없지만, 다른 기프티콘에 대해서는 사용할 계획이 더 앞인 기프티콘이 더 뒤인 기프티콘보다 사용 기한이 더 짧아야 한다
            - 그렇기 때문에 사용할 계획이 가장 앞인 기프티콘부터 연장해야 할 횟수를 구한다
            
            - 사용할 계획 순으로 정렬되어 있으니, 계획이 같지 않는 한 이전에 나온 기프티콘보다 사용 기한이 길어야 한다
            - 그러므로 이전까지 구한 기프티콘들의 최대 사용 기한과 현재 기프티콘의 사용 계획 중 더 큰 숫자를 취하여 이 숫자와 현재 기프티콘의 사용 기한을 비교하여 사용 기한이 해당 숫자를 넘을만큼 30씩 더한다
            - 다음 기프티콘을 확인하기 전에, 만약 다음에 나올 기프티콘의 사용 계획이 현재 기프티콘의 사용 계획과 같을 경우, 이전까지의 최댓값으로 현재 기프티콘의 사용 기한을 업데이트할 필요가 없다
                - 같은 사용 계획에 대해서는 사용 기한에 제약을 받지 않기 때문!
                - 대신 같은 사용 계획 사이에서 가장 큰 사용 기한을 저장해놓는다 -> 다음 사용 계획이 다른 기프티콘에 대해 기준으로 사용하기 위해!
            - 그러나, 다음에 나올 기프티콘의 사용 계획이 현재 기프티콘의 사용 계획과 다를 경우, 이전까지의 최댓값으로 현재 기프티콘의 사용 기한을 갱신한다
            
     */
    static void solution() {
        long answer = 0L;
        int prevMax = giftCards.peek().plan;
        int curMax = 0;

        while(!giftCards.isEmpty()) {
            GiftCard giftCard = giftCards.poll();

            if(prevMax > giftCard.deadline) {
                prevMax = Math.max(prevMax, giftCard.plan);

                int extensionNum = ((prevMax - giftCard.deadline) / 30) + ((prevMax - giftCard.deadline) % 30 == 0 ? 0 : 1);

                answer += extensionNum;
                giftCard.deadline += extensionNum * 30;
            }

            curMax = Math.max(curMax, giftCard.deadline);

            if(giftCards.size() > 0 && giftCard.plan != giftCards.peek().plan) {
                prevMax = curMax;
            }
        }

        System.out.println(answer);
    }

    static class GiftCard implements Comparable<GiftCard> {
        int deadline;
        int plan;

        public GiftCard(int deadline, int plan) {
            this.deadline = deadline;
            this.plan = plan;
        }

        @Override
        public int compareTo(GiftCard o) {
            if(plan != o.plan) {
                return plan - o.plan;
            }
            return deadline - o.deadline;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}