[BaekJoon] 백준 1931번 _회의실 배정 for JAVA _ 그리디 알고리즘

 

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

1931번: 회의실 배정

 

 

문제

 

 

---

 

https://st-lab.tistory.com/243

엄청난 블로그 설명...!! 풀이도 저 블로그에 아주 잘 설명되어있다.~

 

 

알고리즘을 떠올리지 못했다.

 

이런 문제를 풀 때는 그려보는게 짱이다! 라는걸 다시 느낌......~

 

다음부터는 꼭! 그려보도록 하자.. 2주정도 어학성적때매 쉬었더니 감 더 떨어짐

 

 

 

 

 

코드

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

public class Baek1931 {
	public static void main(String[] args) throws IOException {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int meeting = Integer.parseInt(br.readLine());
		int[][] time = new int[meeting][2];
		int count = 0;
		int pre_time = 0;
		
		for(int i = 0; i < meeting; 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]; // 끝나는 시간이 같으면 시작 시간이 작은것부터 정렬
				
				return o1[1] - o2[1]; // 끝나는 시간이 작은 것부터 정렬
			}
		});
		
		for(int i = 0; i < meeting; i++) {
			if(pre_time <= time[i][0]) {
				pre_time = time[i][1];
				count++;
			}
		}
		
		System.out.println(count);
	}
}

 

 

 

 

알게된점

 

 

처음부터 시작시간, 끝시간 배열을 만들어야할지.. 시작시간으로 정렬하고 stack으로 바로 넣어서 비교하는건가.. 심지어 map함수를 써봐야할지 여러 고민을.. 했는데

 

2차원 배열을 만들면 되는구나! 깨달았다.

 

 

그리고

Arrays.sort(T[], Comparator) 이런식으로 할 수 있다는것

 

 

Comparator 사용법!

 

 

 

comparator 사용법

 

 

 

o1과 o2를 비교하여 array 해줌

 

 

설명 대박인 블로그 : https://st-lab.tistory.com/243