[백준] 1931번 : 회의실 배정

문제

느낀점

2차원 배열을 선언해서 입력하는 자료구조를 만들고, 처음으로 BufferedReader를 사용해서 여러 개의 값을 for문으로 계속 받아준 다음, 객체 정렬을 할 때 사용자 정의를 해 줄 수 있는 Comparator 인터페이스의 compare() 추상 메소드를 오버라이딩하여 종료시간 순으로 오름차순으로 정렬해주는 것까진 성공했다.

cf. BufferedReader는 한 번만 선언하고 for문 안에 br변수의 메소드인 readLine()으로 계속 값을 입력 받아줄 수 있다

그러나 문제는 그 이후였다. 종료시간 < 시작시간 인 것들중 최소 종료시간을 구하는 게 어려웠다. 처음 정렬했을 때와 그 이후에 비교를 할 때, 이 과정을 또 한 번 반복해야 하는 건지 고민이 많았는데, 이 부분은 끝내 풀리지 않아 도움을 받았다 (https://st-lab.tistory.com/145).

필요한 것은 종료시간의 변수화를 통한 갱신 이었다.
이미 정렬되어 있는 것을 잘 활용해야 하는데, 이미 끝나는 시간은 빠른 순으로 정렬이 되어 있으므로, 시작시간이 이미 있는 종료시간과 비교했을 때 겹치지 않는 것이 중요하다.
따라서 시작시간이 종료시간보다 같거나 큰 게 나온다면 바로 그것이 다음 회의 시간이 되는 것이다. 그리고 그 다음 회의 시간의 종료시간을 종료시간 변수에 대입해줘서 바로 갱신해준다. 처음부터 끝까지 이것의 반복이다.

그리디 알고리즘이 사용된 문제로 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 최종값이 구해지는 것이다.

풀이

package december_first;

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

public class baek_1931_3 {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int[][] arr = new int[N][2];
		
		// arr에 입력 값 넣어주기
		// 여러 값을 배열에 넣어줄 때 콘솔로 출력되는 무언가가 있으면 안 됨(흐름 끊기면 에러남)
	    for (int i = 0; i < N; i++) {
	    	
	    	// br.readLine() 쓸 때 오류 처리 꼭 해주기
	    	StringTokenizer st = new StringTokenizer(br.readLine()," ");  //br.readLine() 오류 처리
	    	
	    	for(int j = 0; j < 2; j++) {
	    		
	    		// StringTokenizer는 String을 쪼갤 때 사용함 -> Integer.parseInt() 이용해야
	    		// Integer.valueOf(str)은 먹히지 않음
	    		arr[i][j] = Integer.parseInt(st.nextToken());
	    	}
        
	    	
	    }
		
	    Arrays.sort(arr, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
					
				// 종료시간이 같으면 시작 시점 기준으로 오른차순 정렬
				if(o1[1] == o2[1]) {
					return o1[0] - o2[0];
				}
                
                // 1 3
                // 8 8
                // 4 8
                -> 마지막 두 가지의 순서 바꿔줘야 최대 회의 개수 구할 수 있음
					
				return o1[1] - o2[1]; 
				// 두번째 원소들끼리 비교 arr[0][1] vs. arr[1][1]
				// 오름차순으로 정렬 (양수이면 순서 바꿈)
			}
			
		});
	    
		int count = 0;
		int endTime = 0;
	 	
	 	for(int i = 0; i < N; i++) {
	 		
	 		// 종료시간이 다음 회의 시작시간보다 작거나 같으면
	 		if(endTime <= arr[i][0]) {
	 			
	 			// 종료시간을 해당 회의 종료시간으로 갱신
	 			endTime = arr[i][1];
	 			count++;
	 		}
	 		
	 	}
	 	
	 	System.out.println(count);
	 	
	 	
	}

}

References

문제 풀이 참고
https://st-lab.tistory.com/145
Comparable과 Comparator의 이해
https://st-lab.tistory.com/243
2차원 정렬이 쓰인 좌표 정렬 문제
https://st-lab.tistory.com/110#%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
br.readLine()과 st.nextToken()을 int로 형변환해주는 Integer.parseInt()
https://makemethink.tistory.com/171