[백준 1931] 회의실 배정_ 자바Java

문제링크: BOJ 1931

1. 첫 번째 시도 - 틀렸습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Meeting implements Comparable<Meeting> {
	int start;
	int end;

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

	@Override
	public int compareTo(Meeting o) {
		return this.end - o.end;
	}
}

public class Main {

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

		int N = Integer.parseInt(in.readLine());
		Meeting[] meetings = new Meeting[N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			meetings[i] = new Meeting(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		Arrays.sort(meetings);
		int num = 1;
		int e = meetings[0].end;
		for (int i = 1; i < N; i++) {
			if (e <= meetings[i].start) {
				e = meetings[i].end;
				num++;
			}
		}
		System.out.println(num);
		in.close();
	}
}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Meeting implements Comparable<Meeting> {
	int start;
	int end;

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

	@Override
	public int compareTo(Meeting o) {
		return this.end - o.end;
	}
}

public class Main {

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

		int N = Integer.parseInt(in.readLine());
		Meeting[] meetings = new Meeting[N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			meetings[i] = new Meeting(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		Arrays.sort(meetings);
		int num = 1;
		int e = meetings[0].end;
		for (int i = 1; i < N; i++) {
			if (e <= meetings[i].start) {
				e = meetings[i].end;
				num++;
			}
		}
		System.out.println(num);
		in.close();
	}
}

2. 두 번째 시도 - 맞았습니다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Meeting implements Comparable<Meeting> {
	int start;
	int end;

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

	@Override
	public int compareTo(Meeting o) {
		if(this.end == o.end) return this.start - o.start;
		return this.end - o.end;
	}
}

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int N = Integer.parseInt(in.readLine());
		Meeting[] meetings = new Meeting[N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			meetings[i] = new Meeting(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		Arrays.sort(meetings);
		int num = 1;
		int e = meetings[0].end;
		for (int i = 1; i < N; i++) {
			if (e <= meetings[i].start) {
				e = meetings[i].end;
				num++;
			}
		}
		System.out.println(num);
		in.close();
	}
}

3. 해결방안 + 느낀점

Greedy 문제라는 것에서 힌트를 얻을 수 있었다. 회의가 최대한 빨리 끝나서 가능한 한 많은 회의를 열어야 하기 때문에 회의시간이 빨리 끝나는 순으로 정렬을 했다. 그러나, 내가 한가지 간과한 것은 회의 시간이 같은 경우였다.

아래 사진은 내가 질문 검색 게시판을 통해 찾은 반례이다.

사실 이 부분을 알고는 있었지만, 굳이 처리해주지 않아도 Comparable 인터페이스는 default로 오름차순 정렬이 되는 줄 알았다. 하지만, 내가 정의한 클래스이기 때문에 오름차순이 아니라 end값이 같으면 먼저 들어온 순서대로 정렬이 되는 것이었다. 위 예제에서 2번째 회의인 (7, 7)이 (5, 7)보다 나중에 왔다면 괜찮았지만, 여기서는 먼저 입력되기 때문에 내가 생각한대로 정렬이 되지 않는 것이다. 오호! javadoc 다시 꼼꼼하게 읽자..