[백준] 1931번 : 회의실 배정 - 자바(JAVA)

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

문제 해석

한 개의 회의실이 존재하며 회의를 하기 위해서는 회의실을 사용해야 한다.

N개의 회의에 대하여 시작시간과 끝나는 시간이 주어진다.

이때 회의가 겹치지 않으며 최대가 되는 회의의 개수를 찾아보자.

회의가 끝나는 것과 동시에 다음 회의가 시작할 수 있다.

회의의 시작시간과 끝나는 시간이 같을 수도 있다.

 

입력

첫째 줄에 회의의 수 N이 주어진다.

둘째 줄부터 N개의 회의시작시간과 회의 종료시간이 주어진다.

 

제약조건

1 <= N <= 100,000

회의시작시간과 종료시간은 0 또는 2^31 -1보다 작거나 같은 자연수이다.

 

 

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

문제 풀이전 설계

우선 회의 종료 시간을 알아야 하기 때문에 값을 입력받으면서 최댓값을 갱신하여 저장한다.

0초부터 1초씩 증가시키며 반복한다.

 

핵심기능

1. 0초, 1초, 2초, 3초 ... N초에 대한 최적해를 찾고 그것에 대한 점화식을 세워 접근하기

2. 입력값을 기반으로 DP설계

 

자료구조

1. 배열에 저장하여 해당하는 index에 값을 1으로 할당(종료시간이 14라면 14*14의 크기)

2. 특정 자료구조에 저장하여 입력된 만큼의 size를 가짐. (N의 크기)

 

풀이하면서 고민해본점

어떻게 풀어야 할지 막막하여 다른 분들의 풀이를 보았습니다.

다른 분들은 탐욕 법을 이용하여 이 문제를 많이 풀었습니다.

 

1. 회의가 끝나는 시간이 빠른 것을 우선적으로 

(1,4)

(2,10)

(9,10)

(10,10)

(3,6)

(4,8)

 

(회의 시작시간, 회의 종료시간)이다음과 같이 주어진다면  회의가 끝나는 시간이 빠른 것을 우선적으로 정렬합니다.

 

(1,4)

(3,6)

(4,8)

(10,10)

(9,10)

(2,10)

 

int tempFinishTime = 0;
for (Conference c : conferenceList) {
	if (c.startTime < tempFinishTime) {
		continue;
	}
	tempFinishTime = c.finishTime;
	maxConferenceCount++;
}

정렬 후에 위와 같은 로직으로 회의의 최대 개수를 구할 수 있습니다.

 

하지만 이때 문제가 생길 수 있습니다.

바로 회의 끝나는 시간이 같을 때 (1,4) , (4,8), (9,10) (10,10)의 순서를 가진다면

(1,4) 값이 들어가면 tempFinishTime에는 4가 들어가고 maxConferenceCount는 증가합니다.

이후에 (4,8) 값이 들어가면 tempFinishTime에는 8이 들어가고 maxConferenceCount는 증가합니다.

이후에 (9,10) 값이 들어가면 tempFinishTime에는 10이 들어가고 maxConferenceCount는 증가합니다.

이후에 (10,10) 값이 들어가면 tempFinishTime에는 10이 들어가고 maxConferenceCount는 증가합니다.

 

하지만 이때

(10,10), (9,10)의 순서를 가진다면

(10,10) 값이 들어가서 tempFinishTime에 10이 들어가게 되고

이후에 (9,10) 값이 들어가면 c.startTime(9) < tempFinishTime(10) 이므로 continue 되어 count가 증가하지 않습니다.

 

따라서 "2. 회의가 끝나는 시간이 같다면 회의 시작시간이 빠른 것을 우선적으로"가 필요합니다.

이를 통해 (10,10), (9,10)과 같은 값을 (9,10) , (10,10)으로 정렬하여 최대 회의수를 구할 수 있습니다.

 

어려웠던 점

DP로 풀어야 한다고 고정적인 생각을 가지고 있었는데 탐욕 법을 통해 해결할 수 있었다.

Comparable을 interface를 구현하는 법을 자세히 몰라서 이에 대해 알게 되었다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

class Conference implements Comparable<Conference> {
	public int startTime;
	public int finishTime;

	Conference() {
		this(0, 0);
	}

	Conference(int startTime, int finishTime) {
		this.startTime = startTime;
		this.finishTime = finishTime;
	}

	@Override
	public int compareTo(Conference c) {
		if (this.finishTime == c.finishTime) {
			return this.startTime - c.startTime;
		} else {
			return this.finishTime - c.finishTime;
		}
	}
}

public class ConferenceRoomAssignment {

	static int conferenceCount = 0;
	static int maxConferenceCount = 0;
	static List<Conference> conferenceList = new ArrayList<Conference>();

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		inputConferenceInfo();
		if (isConferenceCountZero()) {
			printMaxConrenceCount();
		}
		sortConferenceList();
		getMaxConferenceCount();
		printMaxConrenceCount();

	}

	private static void inputConferenceInfo() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		conferenceCount = Integer.parseInt(br.readLine());

		for (int i = 0; i < conferenceCount; i++) {
			String str = br.readLine();
			StringTokenizer st = new StringTokenizer(str, " ");
			Conference c = new Conference(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			conferenceList.add(c);
		}
		br.close();
	}

	private static boolean isConferenceCountZero() {
		return conferenceCount == 0 ? true : false;
	}

	private static void sortConferenceList() {
		Collections.sort(conferenceList);
	}

	private static void getMaxConferenceCount() {
		int tempFinishTime = 0;

		for (Conference c : conferenceList) {
			if (c.startTime < tempFinishTime) {
				continue;
			}
			tempFinishTime = c.finishTime;
			maxConferenceCount++;
		}
	}

	private static void printMaxConrenceCount() throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(maxConferenceCount + "\n");
		bw.close();
		return;
	}

}