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

알고리즘

• 그리디 알고리즘
• 정렬

1. 문제

2. Idea

• 날짜 비교를 위해 3/1을 301, 12/1을 1201 형식으로 바꾸어 계산한다.

1. 301을 초기 기준 날짜로 설정한다.
2. 301보다 작은 날짜가 start_date인 꽃들 중에서, 가장 늦게 지는 꽃의 end_date를 구한다.
3. 2번에서 구한 가장 늦게 지는 꽃의 날짜를 새로운 기준으로 설정한다.
4. 이 과정을 반복. 가장 늦게 지는 꽃의 날짜가 1130보다 클 경우, 더이상 확인하지 않아도 되면 이를 중단하고, 그 시점 까지의 result를 출력한다.

3. 풀이

3.1. CalDate(String m, String d) 구현

• 날짜 대소 비교를 위해 월과 일을 MMDD 형식의 정수로 변환하는 메서드

    public static int CalDate(String m, String d){
        return (Integer.parseInt(m))*100+Integer.parseInt(d);
    }

3.2. 시작/종료 날짜 지정 및 TreeMap 생성

• 각 꽃의 시작 날짜와 종료 날짜를 저장할 TreeMap 생성

        final int start_date = 301; //시작 날짜
        final int end_date = 1201; //종료 날짜

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); //전체 꽃 종류의 수
        TreeMap<Integer, Integer> flowers = new TreeMap<>();

3.3. 종료 날짜 비교 및 입력 저장

• 각 꽃의 시작 날짜와 종료 날짜를 TreeMap에 저장
  • TreeMap은 정렬 상태를 유지하므로 시작 날짜를 기준으로 정렬된 형태이다.
• 단, 시작 날짜가 같은 경우 종료 날짜가 더 긴 꽃을 저장

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = CalDate(st.nextToken(), st.nextToken()); // 시작 날짜
            int end = CalDate(st.nextToken(), st.nextToken()); // 종료 날짜

            if (flowers.get(start) == null || flowers.get(start) < end) {
                flowers.put(start, end);
            }
        }

3.4.

• current_date를 시작 날짜 (301)로 초기화하고, 종료 날짜 (1201) 이전까지 반복
• 각 반복에서, 현재 기준 날짜 이전 또는 같은 시작 날짜를 가진 꽃 중에서 종료 날짜가 가장 늦은 꽃을 찾는다.
• 유효한 꽃을 찾으면, 기준 날짜를 해당 꽃의 종료 날짜로 갱신하고, result++
• 유효한 꽃을 찾지 못하면, 루프를 중단하고 결과를 0으로 설정

        // 기준 날짜보다 먼저 피는(또는 기준 날짜와 같은 날짜에 피는) 꽃들 중에서 가장 늦게 지는 꽃을 찾았는가?
        boolean flag = false;

        int current_date = start_date;
        int result = 0;
        
        while (current_date < end_date) {
            int max = current_date; //현재 기준 날짜를 기준으로 가장 멀리 피어 있는 꽃의 end_date를 찾기 위함

            for (Map.Entry<Integer, Integer> entry : flowers.entrySet()) {
                // 꽃이 현재 기준 날짜보다 먼저 또는 동시에 피기 시작했는가? && 그 꽃의 종료 날짜가 현재 max 이후인가?
                if (entry.getKey() <= current_date && entry.getValue() > max) {
                    max = entry.getValue();
                    flag = true; //유요한 꽃
                }
            }

            if (flag) { // 유효한 꽃을 찾았다면, 기준을 가장 먼 날짜로 변경
                current_date = max;
                flag = false;
                result++;
            } else { // 유효한 꽃을 찾지 못한 경우 -> result=0;
                result = 0; break;
            }
        }

3.5. 결과 출력

        System.out.println(result);

4. 전체코드

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

public class Week11 {

    public static int CalDate(String m, String d){
        return (Integer.parseInt(m))*100+Integer.parseInt(d);
    }

    public static void main(String[] args) throws IOException {
        final int start_date = 301;
        final int end_date = 1201;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        TreeMap<Integer, Integer> flowers = new TreeMap<>();

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = CalDate(st.nextToken(), st.nextToken());
            int end = CalDate(st.nextToken(), st.nextToken());

            if (flowers.get(start) == null || flowers.get(start) < end) {
                flowers.put(start, end);
            }
        }

        // 기준 날짜보다 먼저 피는(또는 기준 날짜와 같은 날짜에 피는) 꽃들 중에서 가장 늦게 지는 꽃을 찾았는가?
        boolean flag = false;

        int current_date = start_date;
        int result = 0;

        while (current_date < end_date) {
            int max = current_date; //현재 기준 날짜를 기준으로 가장 멀리 피어 있는 꽃의 end_date를 찾기 위함

            for (Map.Entry<Integer, Integer> entry : flowers.entrySet()) {
                // 꽃이 현재 기준 날짜보다 먼저 또는 동시에 피기 시작했는가? && 그 꽃의 종료 날짜가 현재 max 이후인가?
                if (entry.getKey() <= current_date && entry.getValue() > max) {
                    max = entry.getValue();
                    flag = true; //유요한 꽃
                }
            }

            if (flag) { // 유효한 꽃을 찾았다면, 기준을 가장 먼 날짜로 변경
                current_date = max;
                flag = false;
                result++;
            } else { // 유효한 꽃을 찾지 못한 경우 -> result=0;
                result = 0; break;
            }
        }
        System.out.println(result);
    }
}