[백준] 2457번 - 공주님의 정원 [Java]

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

 

[백준] 2457번 - 공주님의 정원 [Java]

[백준] 2457번 - 공주님의 정원 [Java]

---

1.  아이디어

 

그리디 알고리즘으로 해결할 수 있었다.
시작일에 대한 오름차순 정렬 우선순위 큐와 종료일에 대한 내림차순 우선순위 큐 두 개를 활용해서 3월 1일부터 피어있는 꽃 중 가장 지는 날이 늦을 꽃을 선택하고 현재 날짜를 갱신 후 다시 현재 날짜에 피어 있는 꽃 중 가장 지는 날이 늦은 꽃을 선택하는 과정을 반복했다.

---

2. 문제풀이

 

최초 모든 꽃은 시작일에 대한 오름차순 우선순위 큐에 담았다.
이후 현재 날짜를 3월 1일로 세팅해서 3월 1일에 피어져 있는 꽃들을 임시 우선순위 큐에 담고 이 중 가장 지는 날이 늦은 꽃 하나만 선택했다. 이후 현재 날짜를 다시 갱신하고 현재 날짜 기준 피어져 있는 꽃들을 다시 임시 우선순위 큐에 담는 과정을 반복하도록 구현했다.
계산의 편의를 위해 월 * 100 + 일 형식으로 날짜를 처리했고 11월 30일까지 꽃이 피어야 하는 조건만 주의해서 구현하면 됐다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {

    private static class Day {
        int start;
        int end;

        public Day(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        PriorityQueue<Day> days = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.start, o2.start));
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int m1 = Integer.parseInt(st.nextToken());
            int d1 = Integer.parseInt(st.nextToken());
            int m2 = Integer.parseInt(st.nextToken());
            int d2 = Integer.parseInt(st.nextToken());

            // 지는 날이 3월 이전이거나 피는 날이 12월이면 필요 없는 꽃
            if (m2 < 3 || m1 == 12) continue;

            days.add(new Day(m1 * 100 + d1, m2 * 100 + d2));
        }

        int cnt = 0;
        int end = 301;

        while (!days.isEmpty()) {
            // 임시 우선순위 큐
            PriorityQueue<Day> tmp = new PriorityQueue<>((o1, o2) -> Integer.compare(o2.end, o1.end));
            while (!days.isEmpty() && days.peek().start <= end) {
                tmp.add(days.remove());
            }

            // 임시 우선순위 큐가 비는 상황은 연속되게 피도록 선택할 수 없는 경우
            if (tmp.isEmpty()) break;

            end = tmp.remove().end;
            cnt++;

            if (end >= 1201) break;
        }

        if (end >= 1201) System.out.println(cnt);
        else System.out.println(0);
    }
}

---

4. 후기