[BOJ] 2457 공주님의 정원

✨ 그리디 & 정렬 

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

2457번: 공주님의 정원

---

📍 고려해야할 점

• 날짜를 비교하기 위해 입력으로 주어진 정보를 대소비교 가능하게끔 정수로 바꾸기
• 3/1 ~ 11/30 까지만 확인하면 된다.
• 꽃이 지는 날에는 꽃을 볼 수 없다. 
• 입력으로 주어진 날짜를 꽃이 핀 날짜가 이른 순, 만약 핀 날짜가 같다면 진 날짜가 이른 순으로 정렬시켜야 한다. 

 

🕹️ 풀이 과정

못 풀어서 풀이를 보고 다시 풀었다. 

Olympiad>한국정보올림피아드> 한국정보올림피아드시․도지역본선>지역본선 2011>초등부 3번

 

이렇게 초등부 문제를 못 풀면 좀 허탈하다. 그리디랑 DP 문제는 코드 길이가 짧은 편인데 코드로 한 번에 구현하기 제일 어려운 것 같다..🥲

---

 

🔹 입력으로 주어진 날짜 정렬하기 

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

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

    public int compareTo(Info o){
        if(start==o.start) return end-o.end;
        else return start-o.start;
    }
}

꽃이 핀 날짜가 이른 순서대로 정렬하되 만약 날짜가 같다면 꽃이 진 날짜가 이른 순서대로 정렬한다. 

 

🔹 날짜를 숫자로 변경하기 

for(int i=0; i<N; i++){
    st = new StringTokenizer(br.readLine());

    int startMonth = Integer.parseInt(st.nextToken());
    int startDay = Integer.parseInt(st.nextToken());
    int endMonth = Integer.parseInt(st.nextToken());
    int endDay = Integer.parseInt(st.nextToken());

    int start = startMonth * 100 + startDay;
    int end = endMonth * 100 + endDay;
    dates[i] = new Info(start, end);
}

입력으로 주어진 날짜를 비교하기 위해 숫자로 변형한다. 

예를 들어 3월 1일이라면 301, 5월 26일이라면 526으로 바꾸어서 풀면 대소비교가 보다 쉽다. 

 

🔹 꽃을 볼 수 있는 날짜 탐색하기 

int cnt=0;
int startDay = 301;
int endDay = 1201;
int idx=0;
int end=0;

while(startDay<endDay){

    boolean check=false;

    for(int i=idx; i<N; i++){
        Info d = dates[i];

        if(d.start>startDay) break;
        if(d.end>end){
            end = d.end;
            idx = i+1;
            check=true;
        }
    }

    if(check){
        startDay=end;
        cnt++;
    }else break;
}

 

• 시작 날짜는 3월 1일(301), 마지막 날짜는 12월 1일(1201)로 지정해둔다. 👉 11월 30일까지 보기 위해서는 꽃이 지는 날짜가 12월 1일이어야하기 때문이다. 
• 입력으로 주어진 날짜들을 탐색해가며 꽃을 볼 수 있는 날짜인지 아닌지를 확인한다.
  • 만약 dates 중에서 꽃이 피는 날짜가 startDay보다 크다면 꽃을 볼 수 없는 날이 발생하므로 반복문을 빠져나온다.
  • 만약 dates 중에서 꽃이 피는 날짜가 startDay보다 작거나 같고, 꽃이 지는 날짜가 end보다 크다면 꽃을 충분히 볼 수 있기 때문에 end를 갱신한다. 또한 볼 수 있다는 것을 check=true로 나타낸다. 👉 end는 꽃을 볼 수 있는 가장 큰 날짜를 의미한다. 
  • 꽃을 볼 수 있는지에 대한 여부를 판단하고 다시 while문을 반복할 때 우리가 탐색한 바로 다음 날짜부터 시작하면 된다. 그러므로 idx=i+1로 idx를 따로 저장한다. 
• 날짜들을 다 탐색한 후 꽃을 볼 수 있다면 startDay를 갱신하고, 꽃을 볼 수 있는 것을 만족시키기 때문에 개수를 하나 증가시킨다. 

 

 

 

👩‍💻 전체 코드 

public class BOJ_2457_공주님의정원 {

    static class Info implements Comparable<Info>{

        int start, end;

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

        public int compareTo(Info o){
            if(start==o.start) return end-o.end;
            else return start-o.start;
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        Info[] dates = new Info[N];

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());

            int startMonth = Integer.parseInt(st.nextToken());
            int startDay = Integer.parseInt(st.nextToken());
            int endMonth = Integer.parseInt(st.nextToken());
            int endDay = Integer.parseInt(st.nextToken());

            int start = startMonth * 100 + startDay;
            int end = endMonth * 100 + endDay;
            dates[i] = new Info(start, end);
        }

        Arrays.sort(dates);

        int cnt=0;
        int startDay = 301;
        int endDay = 1201;
        int idx=0;
        int end=0;

        while(startDay<endDay){

            boolean check=false;

            for(int i=idx; i<N; i++){
                Info d = dates[i];

                if(d.start>startDay) break;
                if(d.end>end){
                    end = d.end;
                    idx = i+1;
                    check=true;
                }
            }

            if(check){
                startDay=end;
                cnt++;
            }else break;
        }

        if(end<endDay) cnt=0;
        int answer=cnt;
        bw.write(answer + " ");
        bw.flush();
        bw.close();
    }
}