[Algorithm]🐿️99클럽 코테 스터디 5일차 TIL : 백준 2457 공주님의 정원

썸네일

🔍문제

정원

https://www.acmicpc.net/problem/2457
오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.

총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)

이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.

공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다. 
N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오. 

🤔발상

꽃들을 시작 날짜와 종료 날짜로 정렬한 뒤에, 앞에서부터 조건에 맞는지 검사하면서 가장 종료 날짜가 긴 꽃을 선택하면 될 것 같았습니다.
주 키워드는 정렬과 그리디 알고리즘으로 보입니다.

🔦입출력

입력
꽃들의 총 개수 N(1~100,000)
꽃이 피는 날짜와 지는 날짜 x N
출력:  
선택한 꽃들의 최소 개수

📃의사코드

- 입력받은 꽃들을 정렬 가능한 클래스로 생성하여 배열에 담기
- 배열 정렬
- 시작날짜, 종료날짜 기준점 생성
- 시작날짜가 종료날짜 이전 동안 반복
	- 꽃들 배열 탐색
		- 탐색 대상의 시작날짜가 현재 시작날짜보다 늦으면 안됨
		- 탐색 대상의 종료날짜가 현재까지 찾은 마지막 날짜보다 뒤라면
			- 마지막날짜 업데이트
			- 인덱스 업데이트
			- 찾음 플래그 on

👨‍💻코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.time.LocalDate;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

public static void main(String args[]) throws NumberFormatException, IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int n = Integer.parseInt(br.readLine());
            Flower[] flowers = new Flower[n];
            for (int i = 0; i < n; i++) {
                flowers[i] = new Flower(br.readLine());
            }
            Arrays.sort(flowers);
            final int BASE_YEAR = 2023;
            LocalDate start = LocalDate.of(BASE_YEAR, 3, 1);
            LocalDate end = LocalDate.of(BASE_YEAR, 12, 1);

            int count = 0;
            int idx = 0;
            LocalDate maxEnd = start;

            //1. [x]시작날짜, 종료날짜 비교
            //2. [x]선택한 값이 종료날짜 이전인 동안 반복
            //3. [x]탐색 대상의 시작일이 이전 꽃의 이전 꽃의 종료일보다 이후이면 선택 안함
            //4. [x]탐색 대상의 기간이 이전 최대값보다 크면 선택
            while (start.isBefore(end)) {
                boolean find = false;
                for (int i = idx; i < n; i++) {
                    if (flowers[i].getStart().isAfter(start)) {
                        break;
                    }
                    if (flowers[i].getEnd().isAfter(maxEnd)) {
                        maxEnd = flowers[i].getEnd();
                        idx = i;
                        find = true;
                    }
                }
                if (!find) {
                    count = 0;
                    break;
                }
                start = flowers[idx].getEnd();
                count++;
                idx++;
            }

            bw.write(String.valueOf(count));
        }
    }

}

class Flower implements Comparable<Flower> {

    private final LocalDate start;
    private final LocalDate end;

    Flower(String str) {
        StringTokenizer st = new StringTokenizer(str);
        start = LocalDate.of(2023, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        end = LocalDate.of(2023, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
    }

    public LocalDate getStart() {
        return start;
    }

    public LocalDate getEnd() {
        return end;
    }


    //equals, hashCode, toString 생략
    @Override
    public int compareTo(Flower o) {
        if (this.start.equals(o.start)) {
            return o.end.compareTo(this.end);
        }
        return this.start.compareTo(o.start);
    }
}

🚀TIL

• 처음엔 LocalDate를 좀 더 활용하고 싶어 CronoUtil.DAYS.between(start,end)로 period를 구해서 최적해를 찾아보려 했는데, 시작 날짜에 따라 문제의 최적해가 꽃의 period만으로 판단할 수 없어서 수정하였습니다.
• 날짜를 다루는 알고리즘 문제가 꽤 자주 나오는데, 시간내서 java.time 복습을 해야겠습니다.