BOJ 1931
위 문제는 백준 사이트의 알고리즘 1931 문제에 관한 설명입니다.
문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다.
각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.
단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다.
둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.
시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [][] arr = new int[n][2];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = 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];
}
else return o1[1]-o2[1];
}
});
int time = 0;
int count = 1;
for (int i = 1; i < n; i++) {
if(arr[i][0] < arr[time][1]) continue;
count++;
time = i;
}
System.out.println(count);
}
}
회의수 N과 시작시간, 끝시간을 받아줍니다.
여기서 comparator를 이용해서 정렬을 시켜주는데
arr값을 comparator에서 if문 -> 회의시간이 끝나는 시간이라면 회의 시작 시간으로 정렬
else문 -> 아니라면 끝나는 시간으로 정렬시킵니다.
이후 다음 회의의 시작시간이 현재 회의의 종료시간보다 작다면 continue; 아니라면 횟수를 늘려주고 현재시간을 i로 잡아줍니다.
위 영상을 참고하면 이해하기 더 쉽습니다.
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner= new Scanner(System.in);
int n = scanner.nextInt();
int[][] arr = new int[n][2];
for (int i = 0; i < n; i++) {
arr[i][0] = scanner.nextInt();
arr[i][1] = scanner.nextInt();
}
Arrays.sort(arr, 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 time = 0;
int count = 1;
for (int i = 1; i < n; i++) {
if(arr[i][0] < arr[time][1]) continue;
count++;
time = i;
}
System.out.println(count);
}
}
처음에 풀었던 방식입니다.
메모리 165484KB 시간은 1052ms가 걸려서 버퍼를 사용했습니다.
버퍼를 사용하면
메모리 43504KB 시간은 436ms로
메모리는 약 1/4, 시간은 1/2 정도로 줄어들게 되었습니다.