Boj-1931번/java/greedy

문제

풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Math.sqrt;
class MeetingComparator implements Comparator<int[]> {
    @Override
    public int compare(int[] a, int[] b) {
        if (a[1] == b[1]) {
            return Integer.compare(a[0], b[0]);
        }
        return Integer.compare(a[1], b[1]);

    }
}
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());

        int[][] meetings = new int[n][2];
        for(int i=0;i<n;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            meetings[i][0] = Integer.parseInt(st.nextToken());
            meetings[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(meetings,new MeetingComparator());

        int count = 0;
        int endTime = 0;
        for (int i = 0; i < n; i++) {
            if (meetings[i][0] >= endTime) {
                endTime = meetings[i][1];
                count++;
            }
        }


        System.out.println(count);

    }
}

 

Arrays.sort 메소드는 두 가지 오버로딩, 하나는 파라미터로 list만을 넘겨받는 것이며,  다른 하나는 Comparator 객체도 함께 넘겨받는 아래의 형태.

 

Comparator는 함수형 인터페이스로 두 가지 객체를 비교하는 compare를 구현하도록 강제하고 있음. compare은 두 객체 중 앞의 것이 작으면 음수 같다면 0, 크다면 양수를 반환해야함. 함수형 인터페이스인 Comparator를 MeetingComparator라는 class로 구현했음

 

 

#개선사항

 

 람다식 혹은 익명 클래스로 구현을 할 수 있음(이 익명 클래스를 밖으로 빼낸 형태가 내가 구현한 일반 클래스 형태 )

Comparator<int[]> meetingComparator = new Comparator<int[]>() {
    @Override
    public int compare(int[] a, int[] b) {
        if (a[1] == b[1]) {
            return Integer.compare(a[0], b[0]);
        }
        return Integer.compare(a[1], b[1]);
    }
};

Arrays.sort(meetings, meetingComparator);

 

람다식 구현

//형태 1
Comparator<int[]> meetingComparator = (a, b) -> {
    if (a[1] == b[1]) {
        return Integer.compare(a[0], b[0]);
    }
    return Integer.compare(a[1], b[1]);
};

Arrays.sort(meetings, meetingComparator);


//형태 2
Arrays.sort(meetings, (a, b) -> {
            if (a[1] == b[1]) {
                return Integer.compare(a[0], b[0]);
            }
            return Integer.compare(a[1], b[1]);
        });

 

 

#참고사항

Comparator에 대한 개념이 명확하지 않았는데 그 내용은 아래 내용을 참고했다.

https://jaehee329.tistory.com/11

[Java] Comparator 구현부터 디폴트 메서드까지 활용해 정렬하기

 

 

#부족한점

이차원배열,  Comparator 에 대한 연습이 더 필요하다.