[Java] 백준 1931. 회의실 배정

정석·2024년 5월 22일

알고리즘 학습

목록 보기

49/67

Comparable & compareTo

🧑🏻‍💻 문제

회의를 할 수 있는 회의실이 딱 한 개 존재한다.

여러 개(N 개) 의 회의 시간(시작 시간, 끝 시간)에 대한 정보를 준다.

회의 시간은 서로 겹칠 수 없을 때 가장 많은 회의를 진행하면 몇 번의 회의를 할 수 있을까?

단, 회의의 시작 시간과 끝나는 시간이 같을 수도 있다. (매우 중요!)

사실 문제를 읽으면 머릿속에서 구현하는 건 생각보다 간단했다.

최대한 회의를 많이 진행하려면 빨리 끝나는 회의 부터 진행하면 되고, 겹치지 않게 시작시간과 끝 시간을 잘 고려하여 조합하면 된다.

그래서 처음엔 이렇게 생각했었다.

각 회의별 걸리는 시간
시작, 끝 시간

Map을 활용해 값을 맵핑하자니 정렬하려면 다시 List로 꺼내서 정렬하고... 결국 마땅한 방법이 아닌 거 같아 다른 사람들의 풀이를 참고하였다.

💡 핵심

일단, 빨리 끝나는 회의 를 생각하려면 종료 시간 이 빨라야 한다.
그 이후에 시작시간과 고려하여 겹치지 않도록 한다.

그럼 회의 리스트를 나열해 봤을 때, 종료 시간이 빠른 순(수가 작은 순서)
즉, 오름차순으로 정렬할 필요가 있다.

정리해 보면

회의 시간을 종료 시간 기준으로 오름차순 정렬한다.
이전 회의 종료 시간과 새롭게 시작 될 회의 시작 시간과 겹치지 않을 때 count++

2-1. 단! 회의의 시작 시간 = 종료 시간 인 경우도 존재하므로 그럴 경우엔 앞선 회의의 종료 시간과 겹칠 수도 있음.
따라서 정렬을 하다가 회의 시간의 종료 시간 이 같을 땐 시작 시간 을 비교하여 시작 시간이 빠른 것 부터 우선 진행할 수 있도록 한다. (아래 그림 참조)

그림에서 볼 수 있듯이 (0,4) 회의와 (4,4) 회의가 존재할 때, 종료 시간으로만 오름차순 정렬해서 만약 (4,4) 회의가 우선 진행 되면 (0,4) 회의는 진행하지 못하게 된다.
그러므로 종료시간이 같을 땐 시작시간이 빠른 것 부터 정렬해야 한다.

근데, 회의시간은 단순한 정수 배열이 아니라 (1,3), (5,7) 과 같은 값이 여러개인 구조인데 종료 시간 기준으로 어떻게 정렬할까?

java 인터페이스의 Comparable 를 활용하여 Arrays.sort 를 내 맘대로 바꿔서 사용하면 된다.

Comparable ?

간단하게 설명하자면, 비교하는 방법인 나만의 비교자 = compareTo 를 만들어 정렬하는 방법을 만들어 줄 수 있도록 해주는 인터페이스이다.

문제에서의 각 회의 시간을 저장할 수 있도록 Meeting 이라는 클래스를 만들어 Comparable 를 구현하면 Meeting 클래스로 만들어진 인스턴스들에 대해 내가 정의한 비교자 를 이용해 정렬할 수 있게 해준다.

Meeting Class

class Meeting implements Comparable<Meeting> {
	long start; // 회의 시작 시간
	long end; // 회의 종료 시간
	
	public Meeting(long start, long end) {
		this.start = start;
		this.end = end;
	}
    
	@Override
	public int compareTo(Meeting o) { // -1 이 되면 오름차순 / 1이 되면 내림차순
    
		// 끝 시간이 같을 경우엔 시작 시간을 오름차순 정렬
		if (this.end == o.end) { 
			return Long.compare(this.start, o.start);
		}
        
        // 그렇지 않다면, 그냥 끝 시간을 오름차순 정렬
		return Long.compare(this.end, o.end);
	}
}

compareTo 의 로직을 살펴 볼 필요가 있다.

compareTo

해당 메서드는 return 값에 따라 정렬하게 된다.

-1 이 반환되면 값이 오름차순으로 정렬
1 이 반환되면 내림차순 정렬

compare

compare(a, b) 에서 a 와 b 의 크기를 비교하여 a가 크면 1, 작으면 -1 을 반환한다.

따라서 compareTo 메서드를 통해 각 인스턴스의 값 하나씩 비교할 수 있게 됐다.

이제 이후의 로직은 간단하다. Arrays.sort 를 통해 Meeting 클래스로 정의된 인스턴스를 정렬하면 compareTo 에서 구현한대로 오름차순 정렬이 된다.

전체 코드에 대한 설명을 하자면

Meeting 클래스로 각 회의 인스턴스 생성하여 시작, 끝 시간 저장
만들어진 인스턴스들을 배열에 담고
그 배열을 Arrays.sort 하여 정렬
회의 첫 시작은 0초이기에 0초부터 시작하여 정렬된 N 개의 회의를 모두 살펴보며 적합한 회의를 선택, 선택할 때마다 count+1

적합한 회의 = 새롭게 시작할 회의의 시작 시간이 앞서 종료된 회의의 종료 시간보다 빠르면 안된다. (겹치기 때문)

마지막으로, count 출력하고 종료.

💡 전체 코드

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()); // 회의 수
		Meeting[] meetArr = new Meeting[N]; // Meeting 인스턴스 담을 배열
		
		for (int i = 0; i < N; i++) { // 회의 정보 입력 및 저장
			StringTokenizer st = new StringTokenizer(br.readLine());
			long start = Integer.parseInt(st.nextToken());
			long end = Integer.parseInt(st.nextToken());
			
			meetArr[i] = new Meeting(start, end);
		}
		
        // compareTo로 정렬됨
		Arrays.sort(meetArr);
		
		int count = 0; 
		long preEnd = 0; // 종료된 회의 종료 시점을 저장할 변수
		
		for (int i = 0 ; i < N; i++) {
        	// 이전의 회의 종료시점과 이후 회의의 시작 시간과 겹치지 않을 때
			if (preEnd <= meetArr[i].start) {
				count++;
                // 새롭게 회의가 추가 되었으니 종료 시점도 변경
				preEnd = meetArr[i].end;
			}
		}
		
		System.out.println(count);
		
	}
		
}

class Meeting implements Comparable<Meeting> {
	long start;
	long end;
	
	public Meeting(long start, long end) {
		this.start = start;
		this.end = end;
	}

	@Override
	public int compareTo(Meeting o) {
		// -1 이 되면 오름차순 / 1이 되면 내림차순
		if (this.end == o.end) {
			return Long.compare(this.start, o.start);
		}
		return Long.compare(this.end, o.end);
	}
}