[Java/Python] 백준 1931번 - 회의실 배정

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

1931번: 회의실 배정

 

혼자 힘으로 풀었는가? : Python - O / Java - X

알고리즘 분류
 - 그리디 알고리즘
 - 정렬

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

 

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

 

---

 

처음 보자마자 입력조건의 모양을 보고 그래프 문제인가.. 싶었는데

 

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

 

주어진 시간들을 시작시간과 종료시간 둘 다 정렬한 후 종료시간과 시작시간을 순차적으로 비교하여 카운트를 증가해주면 된다.

 

1. 시간초과 케이스

처음엔 단순히 생각하여 문제를 풀었다.

 

그리디 알고리즘이기에 모든 경우의 수를 탐색해야 했고 2중 반복문을 통해 문제를 풀었었다.

 

import sys
input = sys.stdin.readline

n = int(input())
data = []
for i in range(n):
  lst = list(map(int, input().split()))
  data.append(lst)
  
data.sort(key=lambda x:x[0])
cnt = 0

for i in range(n):
  tmp_cnt = 1
  start = data[i][0]
  end = data[i][1]
  for j in range(i+1, n):
    if data[j][0] < end:
      continue
    end = data[j][1]
    tmp_cnt += 1
  if cnt < tmp_cnt:
    cnt = tmp_cnt

print(cnt)

결과는 시간 초과

 

2. 배열에 넣는 방식

위의 방법에서 고민을 하다가 굳이 2중반복문을 돌릴 필요가 없으며

 

위에서는 시작시간만 정렬하였으나 종료시간까지 같이 정렬이 필요하다고 생각했다.

 

import sys
input = sys.stdin.readline

n = int(input())
data = []
for i in range(n):
  lst = list(map(int, input().split()))
  data.append(lst)
  
data.sort(key=lambda x:x[0])
data.sort(key=lambda x:x[1])
ans = [[data[0][0], data[0][1]]]

for i in range(1, n):
  if ans[len(ans)-1][1] <= data[i][0]:
    ans.append(data[i])

print(len(ans))

 

3. 좀더 간결한 방식

배열에 넣은 이유는 마지막 값을 알기 위해, 그리고 정답을 출력하기 위해서 넣었는데

 

다시 좀더 생각해보니 굳이 배열에 넣을 필요 없이 종료시간을 따로 관리해주면 되는 거였다.

 

(Python 코드)

import sys
input = sys.stdin.readline

n = int(input())
data = []
for i in range(n):
  lst = list(map(int, input().split()))
  data.append(lst)
  
data.sort(key=lambda x:x[0])
data.sort(key=lambda x:x[1])
end = data[0][1]
cnt = 1
for i in range(1, n):
  if end <= data[i][0]:
    cnt += 1
    end = data[i][1]

print(cnt)

 

(Java 코드)

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

public class Main {
	static Queue<Integer> q = new LinkedList<>();
	static int [] visited = new int[100001];
	public static void main(String[] args) throws NumberFormatException, IOException   {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		int [][] data = new int[n][2];
		for(int i=0; i<n; i++) {
			String s = br.readLine();
			String [] arr = s.split(" ");
			data[i][0] = Integer.parseInt(arr[0]);
			data[i][1] = Integer.parseInt(arr[1]);
		}
		Arrays.sort(data, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				if(o1[1] == o2[1]) {
					return o1[0] - o2[0];
				}
				return o1[1]-o2[1];
			}
		});

		int cnt = 1;
		int end = data[0][1];
		for(int i=1; i<n; i++) {
			if(end <= data[i][0]) {
				cnt++;
				end = data[i][1];
			}
		}
		System.out.println(cnt);
	}
}

참고로 자바로 문제를 풀 때

 

정렬을 어떻게 해야 하지... 싶었다.

 

그래서 검색했다. 정렬하는 방식만 파이썬과 다르고 나머지는 동일하다.

 

 

 

Git 백준 1931번 - 회의실 배정.py

Git 백준 1931번 - 회의실 배정.java