문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.
예제 입력 1
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
예제 출력 1
4
나의 풀이
그리디 알고리즘을 사용하는 문제로 처음에는 회의를 진행하는 시간이 작은 것들을 많이 넣으면 될까 생각을 하고 주어지는 두 시간들의 차이를 배열에 저장하고 정렬을 한 뒤 어떻게 해보려했다... 하지만 역시나 안됐다. 그래서 생각을 해보니 회의의 종료시간이 빠른 것부터 넣어가다보면 될 것같았다. 그래서 주어지는 회의 시간들을
종료되는 시간을 기준으로 정렬
을 하고 시작시간을 비교하여 최대의 개수를 구했다. 이렇게 코드를 짜니까 예제로 주어지는 문제는 풀려서 답안 제출을 해보니 채점이 진행되다가 '틀렸습니다'가 나와 한참동안 또 생각에 잠겼었다. 알고보니 역시나종료시간이 같을때가 문제
였다. 가령 예를 들어보면 다음과 같다.2 2 0 2 1 2 이렇게 배열이 정렬이 되었다고 친다면 앞에서 짠 코드로는 '2 2'에서만 카운트가 되고 뒤에 '0 2,1 2'는 무시가 될 것이다. 결과적으로 count는 1이 증가한다. 그러나 아래와 같다면? 0 2 1 2 2 2 이렇게 정렬이 된다면 count는 2가 증가한다. 왜냐하면 '0 2'에서 카운트가 증가하고 '1 2'는 무시하고나서 '2 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;
/**
* 1931번 회의실배정
*/
public class Baeckjun1931 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] meeting = new int[n+1][2];
int endtime = 0;
int count = 0;
StringTokenizer st = null;
for (int i=1; i<=n; i++) {
st = new StringTokenizer(br.readLine());
meeting[i][0] = Integer.parseInt(st.nextToken());
meeting[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(meeting, new Comparator<int[]>() {
@Override
public int compare(int[] ints, int[] t1) {
if (ints[1] == t1[1])
return ints[0] - t1[0];
else
return ints[1] - t1[1];
}
});
for (int i=1; i<=n; i++) {
if (endtime <= meeting[i][0]) {
endtime = meeting[i][1];
count += 1;
}
}
System.out.println(count);
}
}
'Programming > Algorithm' 카테고리의 다른 글
[백준5086번] 배수와 약수 (0) | 2020.01.18 |
---|---|
[백준1541번] 잃어버린 괄호 (0) | 2020.01.17 |
[백준12865번] 평범한 배낭 (0) | 2020.01.15 |
[백준9251번] LCS (Long Common Subsequence) (0) | 2020.01.12 |
[백준2565번] 전깃줄 (0) | 2020.01.11 |