[백준/Java] 2457 : 공주님의 정원

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

 

이번 문제는 그리디 알고리즘입니다. 문제에서 3월1일부터 11월 30일까지는 꽃이 하나 이상 피어있어야 된다고 했으므로 초기값은
3월1일을 포함하여 이 전까지 핀 꽃 중에 제일 오래사는 꽃이 필요합니다.

 

그리고 제일 오래사는 꽃을 찾게 된다면 그 꽃이 죽는 날을 기준으로 위 행동을 반복하면 됩니다.

 

여기서 해당 꽃이 11월 31일까지 살게 된다면 기록했던 꽃의 수를 반환을 하고 최종적으로 11월 31일까지 못갔다면 0을 반환하면 됩니다. 그리고 만약 꽃이 없는 기간이 생기게 되면 이 또한 바로 0을 반환하면 됩니다.

 

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

public class Backjoon_2457_공주님의_정원 {
    public 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(this.start == o.start){
                return o.end - this.end;
            }
            return this.start - o.start;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Flower> pq = new PriorityQueue<>();

        int startValue = 31;
        int endValue = 1130;
        int answer = 0;

        for(int i = 0; i < N ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            String str1 = st.nextToken();
            String str2 = st.nextToken();
            if(str2.length() == 1){
                str2 = 0 + str2;
            }
            String str3 = st.nextToken();
            String str4 = st.nextToken();
            if(str4.length() == 1){
                str4 = 0 + str4;
            }
            int start = Integer.parseInt(str1 + str2);
            int end = Integer.parseInt(str3 + str4);

            if(end <= startValue || start > endValue) continue;

            pq.offer(new Flower(start, end));
        }

        if(pq.size() == 0){
            System.out.println(0);
        }

        int value = 301;

        while(!pq.isEmpty()){
            int max = 0;
            boolean check = false;
            while(!pq.isEmpty()){
                Flower flower = pq.peek();
                if(value >= flower.start){
                    pq.poll();
                    check = true;
                    max = Math.max(max, flower.end);
                }else{
                    break;
                }
            }
            if(!check) break;

            answer++;
            value = max;
            if(value > endValue) break;
        }
        if(value > endValue){
            System.out.println(answer);
        }else{
            System.out.println(0);
        }
    }
}