[BOJ] 1931 회의실 배정

BOJ 1931

난이도 : 실버 2
유형 : 그리디 알고리즘

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

문제

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

입력

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

출력

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

풀이

• 첫번째 시도
  파이썬으로 풀었을 때는 람다식을 간단히 써서 끝나는 시간을 기준으로 배열을 오름차순 정렬하고 끝나는 시간이 같을 시 시작하는 시간을 기준으로 오름차순 정렬하도록 구현했었다.
  근데 나는 아직 자바의 comparator를 쓸줄 몰라서 일단 하드코딩으로 직접 배열값을 비교하면서 정렬해주었는데 역시나 시간초과가 났다.
• 두번째 시도
  결국 구글링으로 comparator를 검색해서 찾아보았고, 생각보다 어렵지않게 구현할 수 있었다. 어려워서 못한게아니라 게을러서 숙지하지 않았던것 같다... 파이썬과 크게 다르진 않았다. 물론 파이썬이 더 구현하기 더 편하다..

코드

1. 시간초과 풀이

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

/**
 * BOJ_1931_S2_회의실 배정
 * @author mingggkeee
 * 그리디 알고리즘
 */

public class Main {
	
	static int N;
	static ArrayList<Integer>[] time;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine()); // 회의실 개수
		time = new ArrayList[N];
		
		for(int i=0; i<N; i++) {
			time[i] = new ArrayList<>();
		}
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			time[i].add(Integer.parseInt(st.nextToken()));
			time[i].add(Integer.parseInt(st.nextToken()));
		}
		
		// 회의 끝나는 시간이 빠른순으로 정렬. 끝나는 시간이 같을경우 회의 시작 시간이 빠른순서로 정렬
		int count = 0;
		while(true) {
			count = 0;
			for(int i=0; i<N-1; i++) {
				if(time[i].get(1) > time[i+1].get(1)) {
					ArrayList<Integer> temp = time[i];
					time[i] = time[i+1];
					time[i+1] = temp;
					count++;
				} else if(time[i].get(1) == time[i+1].get(1)) {
					if(time[i].get(0) > time[i+1].get(0)) {
						ArrayList<Integer> temp = time[i];
						time[i] = time[i+1];
						time[i+1] = temp;
						count++;
					}
				} else {
					continue;
				}
			}
			if(count == 0)
				break;
		}
		
		int answer = 0;
		int times = 0;
		for(int i=0; i<N; i++) {
			if(time[i].get(0) > times) {
				times = time[i].get(1);
				answer++;
			}
		}
		System.out.println(answer);
	}

}

2. 맞은 풀이

import java.io.*;
import java.util.*;

/**
 * BOJ_1931_S2_회의실 배정
 * @author mingggkeee
 * 그리디 알고리즘
 */

public class Main {
	
	static int N;
	static int[][] time;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine()); // 회의실 개수
		time = new int[N][2];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			time[i][0] = Integer.parseInt(st.nextToken());
			time[i][1] = Integer.parseInt(st.nextToken());
		}
		
		// 회의 끝나는 시간이 빠른순으로 정렬. 끝나는 시간이 같을경우 회의 시작 시간이 빠른순서로 정렬
		Arrays.sort(time, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[1] == o2[1]) {
					return o1[0] - o2[0];
				} else {
					return o1[1] - o2[1];
				}
			}
		});
		
		int answer = 0;
		int times = 0;
		for(int i=0; i<N; i++) {
			if(time[i][0] >= times) {
				times = time[i][1];
				answer++;
			}
		}
		System.out.println(answer);
	}

}

3. 파이썬으로 풀었었던 풀이(파이썬은 신이야..)

def solution(InputArr):
    answer = 0
    endTime = 0
    for i in range(len(InputArr)):
        if endTime <= InputArr[i][0]:
            endTime = InputArr[i][1]
            answer += 1
    return answer

N = int(input())
InputArr = []

for i in range(N):
    num1, num2 = map(int, input().split())
    InputArr.append([num1, num2])
    
InputArr.sort(key=lambda x: (x[1], x[0]))
print(solution(InputArr))