[백준] 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
Author And Source
이 문제에 관하여([백준] 1931번 : 회의실 배정), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@letsbebrave/백준-1931번-회의실-배정저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)