백준 2457번 - 공주님의 정원

문제

백준 2457번 - 공주님의 정원

아이디어

• 꽃이 피는 날짜를 기준으로 오름차순 정렬한다. 이때 날짜는 계산을 편하게 하기 위해 MMDD 형식으로 저장한다.
• 301(3월 1일)을 시작으로, 해당 날짜 이전에 피기 시작한 꽃들 중 가장 늦게 지는 꽃을 찾아 그 꽃이 지는 날짜를 새로운 시작 날짜로 갱신한다. 이 과정을 반복하여 1201(12월1일)까지의 기간을 모두 커버할 수 있으면 카운팅된 꽃의 개수를, 아니면 0을 출력한다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N log N)

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_2457 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        Flower[] flowers = new Flower[n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int blossomMonth = Integer.parseInt(st.nextToken());
            int blossomDay = Integer.parseInt(st.nextToken());
            int fallMonth = Integer.parseInt(st.nextToken());
            int fallDay = Integer.parseInt(st.nextToken());

            flowers[i] = new Flower(
                    blossomMonth * 100 + blossomDay,
                    fallMonth * 100 + fallDay
            );
        }

        Arrays.sort(flowers);

        int start = 301;
        int end = 1201;

        int curEnd = 0;

        int count = 0;
        int index = 0;

        while (start < end) {

            boolean found = false;
            int nextEnd = curEnd;

            while (index < n && flowers[index].blossomDay <= start) {
                if (flowers[index].fallDay > nextEnd) {
                    nextEnd = flowers[index].fallDay;
                    found = true;
                }
                index++;
            }

            //11월 30일까지 중간에 커버할 수 있는 범위의 꽃이 없다면
            if (!found) {
                System.out.println(0);
                return;
            }

            count++;
            start = nextEnd;
            curEnd = nextEnd;
        }

        System.out.println(count);
    }

    static class Flower implements Comparable<Flower> {
        int blossomDay;
        int fallDay;

        public Flower(int blossomDay, int fallDay) {
            this.blossomDay = blossomDay;
            this.fallDay = fallDay;
        }

        @Override
        public int compareTo(Flower o) {
            return this.blossomDay - o.blossomDay;
        }
    }
}