[Java] 그리디 알고리즘 | 백준 2457 공주님의 정원

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

 

접근 방법

 

3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어있어야 하므로 

꽃 피는 날짜 중 하나는 3월 1일 이하, 지는 날짜 중 하나는 무조건 12월 이상이어야 한다.

3월 1일 이하 날짜에 피는 꽃들 중 어떤 꽃을 골라야 될지 생각해보면, 그 중에서는 무조건 가장 늦게 지는 꽃을 고르는 것이 꽃들의 수를 가능한 적게 하는 조건을 만족시키기 유리하다.

 

그렇게 처음 선택할 꽃을 선정했다면, 그 선택된 꽃의 지는 날짜를 기준으로 다음 선택될 꽃을 선정하면 될 것이다.

구간을 겹칠 수 있게 뽑되, 지는 날짜가 긴 꽃을 선택.

 

과정을 반복하며 카운트를 하고, 지는 날짜가 12월 이상인 꽃을 선택했을 때 반복을 종료하고 카운트를 출력한다.

(그 이전에 선택 규칙에 적합한 꽃이 존재하지 않는다면 즉시 0을 출력하고 프로세스를 종료한다.)

 

이 과정을 가능하게 하려면 꽃을 시작일 기준으로 우선 나열할 수 있어야 하므로 Flower 클래스 내에 시작일 기준으로 꽃을 정렬할 수 있도록 Comparable 인터페이스를 구현한다.

static class Flower implements Comparable<Flower>{
    int[] start = new int[2];
    int[] end = new int[2];

    public Flower(int start_m, int start_d, int end_m, int end_d){
        this.start[0] = start_m;
        this.start[1] = start_d;
        this.end[0] = end_m;
        this.end[1] = end_d;
    }

    //시작일 기준
    @Override
    public int compareTo(Flower other){
        if(this.start[0] != other.start[0]){
            return Integer.compare(this.start[0], other.start[0]);
        }else if(this.start[1]!=other.start[1]){
            return Integer.compare(this.start[1], other.start[1]);
        }else if(this.end[0]!=other.end[0]){
            return Integer.compare(other.end[0], this.end[0]);
        }else{
            return Integer.compare(other.end[1], this.end[1]);
        }
    }
}

 

아래와 같이 main 메서드에서 꽃을 입력 받고 리스트에 넣어 준 뒤 시간일 기준으로 나열시킨다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());

List<Flower> flowers = new ArrayList<>();

StringTokenizer st;
for(int i=0; i < N; i++){
    st = new StringTokenizer(br.readLine());
    int start_m = Integer.parseInt(st.nextToken());
    int start_d = Integer.parseInt(st.nextToken());
    int end_m = Integer.parseInt(st.nextToken());
    int end_d = Integer.parseInt(st.nextToken());
    flowers.add(new Flower(start_m,start_d, end_m, end_d));
}

Collections.sort(flowers);

 

다음으로 현제 기준이 되는 날짜 3월 1일을 담을 수 있는 변수 currentMonth, currentDay를 선언해 주었고, 꽃을 순차적으로 가져오기 위한 index 변수, 꽃 개수를 새기 위한 count 변수를 선언했다.

int currentMonth = 3; int currentDay = 1; int index = 0; int count = 0; // 꽃 개수

 

마지막으로 아래와 같이 처음 생각했던 꽃의 선택과정을 구현하였다. 시작일이 현재 날짜 이하이면서 가장 늦게 지는 꽃을 선택하는 과정이다. 여기서 isLaterDate 메서드가 가장 늦게 지는 꽃을 갱신해주는 역할을 하는데 만약 해당 메서드가 한번도 호출이 되지 않았다면 시작일이 현재 날짜 이하이면서 지는 날짜가 시작일 이후인 꽃이 하나도 존재하지 않는다는 의미이므로 문제의 조건을 만족시키지 않아 종료시켜주어야한다. 이를 처리하기 위해 found 변수를 추가해 주었다.

그렇게 선택된 maxEndMoth, maxEndDay(종료일이 가장 뒤인 꽃)을 currentMonth, currentDay로 업데이트하고 이를 반복한다.

while (currentMonth < 12) {
        int maxEndMonth = currentMonth;
        int maxEndDay = currentDay;
        boolean found = false;

        while(index < flowers.size() &&
                (flowers.get(index).start[0] < currentMonth ||
                (flowers.get(index).start[0] == currentMonth &&
                       flowers.get(index).start[1] <= currentDay))){

            Flower current = flowers.get(index);
            //더 늦으면 갱신
            if(isLaterDate(current.end[0], current.end[1], maxEndMonth, maxEndDay)){
                maxEndMonth = current.end[0];
                maxEndDay = current.end[1];
                found = true;
            }

            index++;

        }

        if(!found){
            System.out.println(0);
            return;
        }

        currentMonth = maxEndMonth;
        currentDay = maxEndDay;
        count++;

    }

    System.out.println(count);
}

private static boolean isLaterDate(int m1, int d1, int m2, int d2){
    if(m1 != m2){
        return m1 > m2;
    }
    return d1 > d2;
}

 

 

느낀점 :

이번 문제는 접근 방법보다 나의 생각을 정확히 코드로 구현하는 과정에서 오래 걸렸는데, 조건을 만족시키지 못 할 경우 0을 출력해야하는 경계 조건들을 체크해야 했던 점이 중요했다. 또한 시작 날짜를 기준으로 나열한 것이 매 선택마다 모든 꽃을 확인하지 않고 현재 날짜 이하에 피는 꽃들만 검토할 수 있게 해 주었다.

그리고 그 현재 시점에서의 최선의 선택이 전체적으로도 최선이 되는 구조로, 다시 백트래킹하지 않아도 되는 그리디 알고리즘 특성에 대한 이해도 잘 할 수 있게 된 것 같다.