[Greedy] Softeer(소프티어) level 3 강의실 배정 java 풀이 (+Comparator에 관하여)

https://softeer.ai/practice/6291

Softeer - 현대자동차그룹 SW인재확보플랫폼

문제 풀이법

1. 이중배열 선언 후 [[시작시간, 끝난시간]] 형태로 저장
2. 끝난 시간을 기준으로 오름차순 정렬
3. 이전에 끝난 시간 <= 현재 시작 시간 일 경우, 강의실 배정이 가능하므로 +1

Comparator에 관하여

Comparator 인터페이스는 두 객체를 비교하는 compare() 메서드를 정의하는 함수형 인터페이스입니다. 이 인터페이스를 구현하여 객체들의 정렬 순서를 사용자 정의할 수 있습니다. 

compare() 메소드는 자신이 다른 객체보다 작으면 음수, 같으면 0, 크면 양수를 반환해야 합니다.

List.sort(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[1], o2[1]);
            }
        });

위 코드의 경우, int[] 타입의 두 변수에서 1번째 인덱스를 비교하여, 오름차순으로 정렬합니다.

 

class에서 사용할 때에는 다음과 같이 사용합니다.

class Person implements Comparable<Person> {
    String name;

    Person(String name) {
        this.name = name;
    }

    @Override
    public int compareTo(Person other) {
        return this.name.compareTo(other.name);
    }
}

Comparable<객체 타입> 을 구현하여

compareTo를 오버라이드 합니다.

이 메서드는 Comparable 인터페이스에 정의된 메서드로, 객체 자신과 다른 객체를 비교할 때 사용됩니다.

이 메서드도 compare()과 마찬가지로 자신이 다른 객체보다 작으면 음수, 같으면 0, 크면 양수를 반환해야 합니다.

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());

        int numOfCourse = Integer.parseInt(st.nextToken());
        List<int[]> timeTable = new ArrayList<int[]>();
        for (int i = 0; i < numOfCourse; i++) {
            int[] course = new int[2];
            st = new StringTokenizer(in.readLine());
            course[0] = Integer.parseInt(st.nextToken());
            course[1] = Integer.parseInt(st.nextToken());
            timeTable.add(course);
        }
        
        timeTable.sort(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[1], o2[1]);
            }
        });

        int answer = 0;
        int previousEndTime = 0;
        for(int[] course : timeTable){
            int startTime = course[0];
            int endTime = course[1];
            if(previousEndTime <= startTime){
                answer++;
                previousEndTime = endTime;
            }
        }
        System.out.println(answer);

    }
}

 

참고 자료

https://www.youtube.com/watch?v=X3Scp46yLek