[백준] 2457. 공주님의 정원

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

2457번: 공주님의 정원

우선 날짜를 다루는 방법은 3월 1일은 301, 11월 30일은 1130로 표현하면 된다. 처음에는 어떤 달은 30일까지 있고, 어떤 달은 31일, 28일까지 있으므로 앞서 언급한 방식으로 처리하면 안되는 게 아닌가? 생각했는데, 어차피 입력으로 주어진 날짜들로 합 계산을 하는 게 아니라 그저 대소 비교만 하기 때문에 상관없다.

 

주의할 점은 다음과 같다.

• 이전 꽃이 지는 날짜를 의미하는 preEnd 변수의 값보다 특정 꽃이 더 일찍 피거나 같은 날 피면, 특정 꽃은 선택될 수 있다. 그런데 이 조건에 해당하는 꽃들 중에 가장 늦게 지는 꽃을 선택해야 한다. 그래야 최소 개수의 꽃을 선택할 수 있다.
• 꽃이 먼저 피는 순으로 정렬하고, 피는 날짜가 같다면 늦게 지는 순으로 정렬한다. 
  ➡️ 따라서 꽃이 피는 날짜가 같을 때 제일 앞의 인덱스에 위치한 꽃만 탐색하고 그 뒤의 꽃들은 탐색할 필요가 없다. (더 일찍 지므로)
• flag 변수를 두어 선택된 꽃이 없으면 0을 출력해야 한다. 만약 flag 변수가 없으면 다음 예제에서 실패한다(무한루프).
  • 202 ~ 503
  • 202 ~ 401
  • 501 ~ 504
  • 507 ~ 1212 (여기를 탐색할 때, preEnd 값이 504인데 now.start 값이 507이다. 그러나 그 사이에 선택된 꽃이 없으므로 flag 변수를 두어 선택된 꽃이 없으면 반복문을 빠져나오도록 해야 한다.)

import java.io.BufferedReader;
import java.io.IOException;

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

// 시간복잡도: O(N) = 100,000
public class Main {

    static int n;
    static List<Flower> flowers = new ArrayList<>();
    static int answer = 0; // 꽃의 최소 개수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) * 100 + Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken()) * 100 + Integer.parseInt(st.nextToken());
            flowers.add(new Flower(start, end));
        }

        Collections.sort(flowers);

        int preEnd = 301;
        int tempEnd = 0;
        int tempStart = 0;
        boolean flag = false;

        for (int i = 0; i < n; i++) {
            Flower now = flowers.get(i);
            if (now.start == tempStart) {
                continue;
            }
            if (now.start <= preEnd) {
                if (now.end > tempEnd) {
                    tempEnd = now.end;
                    tempStart = now.start;
                    flag = true;
                }
            } else {
                if (!flag) { // 선택된 꽃이 없는 경우 break
                    break;
                }
                preEnd = tempEnd; // i-1번째 꽃 선택
                answer++; // 꽃을 선택했으므로 카운트
                flag = false;
                i--; // i-1번째 꽃을 선택한 후에 i번째부터 탐색을 다시 해야 하므로
            }
        }

        if (tempEnd > 1130) {
            System.out.println(++answer);
            return;
        }

        System.out.println(0);
    }

    static class Flower implements Comparable<Flower> {
        int start;
        int end;

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

        @Override
        public int compareTo(Flower o) {
            if (this.start == o.start) {
                return o.end - this.end;
            }
            return this.start - o.start;
        }
    }
}