오답노트 #1931 : 회의실 배정

풀이방법 및 문제점

2022.02.14 (1)

그리디 알고리즘 문제이다.

주어진 회의들을 끝나는 시간을 기준으로 오름차순 정렬한다.

정렬된 순서대로 차근차근 방문하며,

이전 회의와 겹치지 않는다면 즉시 스케줄표에 해당 회의를 추가한다.

그럼 빨리 끝나는 순서대로 차근차근 겹치지 않게 스케줄표에 추가할 수 있다.

 

그런데 87%에서 틀렸습니다가 뜬다.

 

백준에 올라온 다음의 테스트케이스에 대하여 올바른 답을 출력하지 못하는 것을 보고 원인을 알 수 있었다.

5
6 7
6 6
5 6
5 5
7 7
답:5

이 테스트케이스를 찾은 게시글 링크

끝나는 시간이 서로 같은 회의가 포함되어있을 경우를 고려하지 않은 것이 문제였다.

 

끝나는 시간이 동일한 회의끼리는 시작 시간을 기준으로 오름차순 정렬을 해주어야 한다.

그런데 이 이중 정렬을 어떻게 코드로 구현할지 아직 생각이 나지 않는다. 자고 일어나서 수정을 시도해보겠다.

 

2022.02.14 (2)

Comparator를 직접 Override하여 해결하였다.

정답 게시물 바로가기

 

코드

Java(2022.02.14(1))

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		Meeting[] meets = new Meeting[n];
		
		//회의들의 정보 읽어오기
		for(int i = 0; i<n; i++) {
			String[] input = br.readLine().split(" ");
			meets[i] = new Meeting(Integer.parseInt(input[0]), Integer.parseInt(input[1]));
		}
		//회의들을 끝나는 시간 기준으로 오름차순 정렬
		Arrays.sort(meets,Comparator.comparing(o->o.end));
		//답 구하기
		int prevEnd = 0;
		int cnt = 0;
		for(int i = 0; i<n; i++) {
			if(prevEnd<= meets[i].start) {
				cnt++;
				prevEnd = meets[i].end;
			}
		}
		System.out.print(cnt);
	}

}

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