99클럽 코테 스터디 5일차 TIL [Greedy]

- 오늘의 학습 키워드 : Greedy 알고리즘

 

[문제 이름 : 공주님의 정원 (백준 2457, G3)]
문제 url : https://www.acmicpc.net/problem/2457

내가 작성한 코드는 아래와 같다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<Flower> flowers = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) * 100 + Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken()) * 100 + Integer.parseInt(st.nextToken());
            flowers.add(new Flower(start, end));
        }

        // 정렬
        Collections.sort(flowers);

        int count = 0;         // 선택한 꽃의 수
        int currentEnd = 301;  // 현재 덮고 있는 날짜의 끝
        int maxEnd = 301;      // 현재 선택할 수 있는 꽃 중 가장 긴 끝 날짜
        int idx = 0;           // 꽃 리스트의 인덱스

        while (currentEnd <= 1130) { // 목표 날짜인 11월 30일까지 덮어야 함
            boolean found = false;

            while (idx < flowers.size() && flowers.get(idx).start <= currentEnd) {
                // 현재 덮을 수 있는 구간 내에서 가장 긴 끝 날짜 찾기
                maxEnd = Math.max(maxEnd, flowers.get(idx).end);
                found = true;
                idx++;
            }

            // 덮을 수 있는 꽃이 없는 경우
            if (!found) {
                System.out.println(0);
                return;
            }

            count++;
            currentEnd = maxEnd;
//            System.out.println("currentEnd: " + currentEnd);

            // 11월 30일 이후로 덮을 수 있으면 성공
            if (currentEnd > 1130) {
                System.out.println(count);
                return;
            }
        }

        System.out.println(0);
    }

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

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

        // 시작 날짜가 빠른 순으로 정렬
        // 시작 날짜 같다면, 지는 날짜가 긴 순서로 정렬
        @Override
        public int compareTo(Flower f) {
            if(this.start == f.start) {
                return f.end - this.end;
            }
            return this.start - f.start;
        }
    }
}

 

풀이 과정 (풀이 시간 : 2시간)

처음 날짜 입력하는 부분을 어떻게 계산할 수 있을지 작성하다가, 헤매게 되었고 결국 타 블로그를 참고하게 되었다.

1. 월 * 100 + 일로 각 꽃에 대한 정보를 ArrayList에 저장한다. 이때 꽃이 피는 날짜는 오름차순으로, 지는 날짜는 내림차순으로 정렬한다. 최소 꽃을 정해야 하므로 동일하게 꽃이 피기 시작한다면, 늦게 져야 더욱 효율적인 꽃들을 선택할 수 있기 때문이다.

2. 현재 꽃이 지는 날짜의 끝을 currentEnd, 현재 선택할 수 있는 꽃들 중 제일 긴 끝 날짜를 MaxEnd, 꽃 리스트 인덱스 idx, 선택한 꽃의 수 count를 저장한다.
3. 목표 날짜인 11월 30일까지 계속해서 while문을 반복한다. 이때, 인덱스(index)가 꽃 리스트 내에 있으면서, 꽃이 피는 날짜가 현재 꽃이 지는 날짜보다 작거나 같다면 내부에 while문을 돌려 제일 늦게 지는 꽃의 날짜를 maxEnd에 저장한다.

4. currentEnd에 maxEnd값을 저장하고, 11월 30일 이하라면 계속 while문을 돌려 3번 과정을 반복한다.

5. 꽃을 선택할 수 있다면 count를 출력하고, 없다면 0을 출력한다.

내일은 주말에 있을 시험에 대하여 전반적인 전공 과목에 대해 학습할 예정이다.