[BaekJoon] 2457 공주님의 정원 (Java)

1.  문제 링크

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

2.  문제

요약

• 총 N개의 꽃이 있는데, 꽃은 모두 같은 해에 피어서 같은 해에 집니다.
• 하나의 꽃은 피는 날과 지는 날이 정해져있는데, 지는 날에 해당하는 날부터 꽃을 볼 수 없다는 의미입니다.
• N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하려고 합니다.
  1. 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 합니다.
  2. 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 합니다.
• N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 꽃들의 총 개수 N이 입력되고 두 번째 줄부터 N개의 줄에 각 꽃이 피는 날짜와 지는 날짜가 입력됩니다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현됩니다.
• 출력: 첫 번째 줄에 선택한 꽃들의 최소 개수를 출력합니다. 만약 두 조건을 만족하는 꽃들을 선택할 수 없다면 0을 출력합니다.

3.  소스코드

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

// 꽃을 피는 날 기준 오름차순으로, 같다면 지는 날 내림차순으로 정렬
//      피는 날, 지는 날은 (달 * 100 + 일)로 표현
// 시작 일(3/1)부터 종료 일(11/30까지)까지로 설정해놓고 꽃의 배열을 순환
//  해당 꽃이 시작일보다 이후에 피기 시작한다면 꽃을 피는 날 기준으로 오름차순으로 정렬해놨었는데 시작일 이후에 핀다면 3/1부터 펴야 한다는 조건을 만족하지 못함
//      -> break
//  해당 꽃이 시작일 이전 혹은 그 날 피기 시작하는 꽃들을 순회하면서 그 중 지는 날이 가장 긴 꽃을 찾음
//  새 꽃을 찾았다는 것을 나타내기 위해 boolean 타입을 true로 변경
//      그러다 시작일 이후에 피는 꽃이 등장한다면 break
//  새 꽃을 찾았다면 시작일을 지는 날이 가장 긴 꽃의 지는 날로 변경, 선택된 꽃의 개수를 1 증가

public class Main {
    static int N;
    static Flower[] flowers;

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

        N = scanner.nextInt();
        flowers = new Flower[N];

        for(int idx = 0; idx < N; idx++) {
            int startMonth = scanner.nextInt(), startDay = scanner.nextInt();
            int endMonth = scanner.nextInt(), endDay = scanner.nextInt();

            int start = startMonth * 100 + startDay;
            int end = endMonth * 100 + endDay;

            flowers[idx] = new Flower(start, end);
        }
    }

    static void solution() {
        Arrays.sort(flowers);

        int start = 301, end = 1201;
        int count = 0, max = 0, index = 0;

        while(start < end) {
            boolean hasNext = false; // 새 꽃 찾은지 여부

            for(int idx = index; idx < N; idx++) {
                // 종료일이 시작일이 이후면 의미 없음. 종료일에는 시작해야 이어지기 때문
                if(flowers[idx].start > start) break;

                if(max < flowers[idx].end) {
                    hasNext = true;
                    max = flowers[idx].end;
                    index = idx + 1;
                }
            }

            if(hasNext) {
                start = max;
                count++;
            } else break;
        }

        if(max < end) System.out.println(0);
        else System.out.println(count);
    }

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

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

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

    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());
        }
    }
}

4.  접근

• 꽃을 나타낼 Flower 클래스를 정의합니다.
  • 꽃의 피는 날짜를 나타내는 변수 start와 지는 날짜를 나타내는 변수 end를 멤버 필드로 갖습니다.
    • 각 날짜는 ((월 * 100) + 일)의 int형 숫자로 나타냅니다.
  • 이후에 Flower 배열을 정렬할 것인데, 이 때 정렬 기준을 잡아주기 위해 Comparable을 구현합니다.
    • 피는 날짜 기준 오름차순으로, 만약 피는 날짜가 같다면 지는 날짜 기준 내림차순으로 정렬합니다.

• 주어진 꽃의 정보를 Flower 객체로 만들어 Flower 배열인 flowers에 저장하고 이를 정렬 기준에 따라 정렬합니다.
• 3월 1일부터 11월 30일까지는 꽃이 피어있어야 하므로 우선 꽃이 피어있어야 하는 기간의 시작 날짜인 3월 1일을 start 변수에 담고 지는 날인 12월 1일을 end 변수에 담습니다.
• 선택한 꽃의 개수를 나타내는 변수 count, flowers 배열의 Flower 객체들을 순회하면서 꽃이 지는 날 중 가장 늦은 날을 저장할 변수 max, 다음 탐색 때 시작할 위치를 나타내는 변수 index를 생성하고 모두 값을 0으로 초기화합니다.
• start의 값이 end 값보다 작을 동안 값을 갱신하면서 꽃들의 최소 개수를 구합니다.
  • 다음 선택할 꽃을 찾았는지 여부를 나타내는 hasNext 변수를 생성하고 false로 값을 초기화합니다.
  • flowers 배열에서 index번째부터 이후의 모든 Flower 객체를 순회하면서 다음 선택할 꽃을 찾습니다.
    • max 값이 현재 Flower 객체의 지는 날보다 작다면 해당 Flower 객체를 우선 선택해봅니다.
      • max 값이 더 작기 때문에 max 값을 현재 Flower 객체의 지는 날로 갱신합니다.
      • 선택된 꽃이 있기 때문에 hasNext 값을 true로 변경합니다.
      • 현재 꽃을 우선 선택했기 때문에 index 값을 (현재 꽃의 인덱스 + 1)로 갱신합니다.
    • 이후의 꽃들도 순회하면서 위 작업을 반복합니다.
    • 그러다 현재 Flower 객체의 피는 날이 start의 값보다 크다면 순회를 멈춥니다.
  • 만약 선택한 꽃이 있다면 start 값을 max 값으로 갱신하고 count 값을 1 추가합니다.
  • 만약 선택한 꽃이 없다면 중간에 꽃이 피지 않는 날이 존재한다는 뜻이므로 반복문을 빠져나옵니다.
• 위 작업을 완료한 후에 max 값이 end 값보다 작다면 결국 11월 30일 이전에 모든 꽃이 지거나 중간에 꽃이 피지 않는 날이 존재한다는 뜻이므로 0을 출력합니다.
• 그렇지 않다면 count 값을 출력합니다.