이 목표는 가장 많은 강의 수를 구하는 문제인데, 곰곰히 생각해보면 제일 먼저 따져야할 것은 끝나는 시간이 가장 빠른 것을 기준으로 정하면 되는 문제이다. 다만 중요한 점은 정말 당연한 이야기이지만 다음 강의의 시작시간이 현재 강의의 끝 시간보다 커야한다는 점이다. 왜? 강의는 겹칠 수가 없으니까.
문제에는 정렬되어서 나온다는 말이 없기 때문에 정렬을 해야한다. 기준은 끝나는 시간을 기준으로 정렬을 하되, 만약 끝나는 시간이 같다면 시작시간이 빠른 순으로 정렬을 하면 된다. 이에 대한 정렬 코드는 아래의 코드이다.
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] start, int[] end) {
if (start[1] == end[1]) {
return Integer.compare(start[0], end[0]);
}
return Integer.compare(start[1], end[1]);
}
});
전체 코드 :
public class BaekJoon_17_1931 {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(reader.readLine());
int[][] arr = new int[n + 1][2]; // 0:시작 시간, 1:끝 시간
StringTokenizer st;
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(reader.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[] start, int[] end) {
if (start[1] == end[1]) {
return Integer.compare(start[0], end[0]);
}
return Integer.compare(start[1], end[1]);
}
});
int count = 0;
int end_time = Integer.MIN_VALUE;
for (int i = 1; i <= n; i++) {
int start_time = arr[i][0];
if (start_time >= end_time) {
end_time = arr[i][1];
count++;
}
}
writer.write(count + "");
writer.flush();
reader.close();
writer.close();
}
}
'알고리즘' 카테고리의 다른 글
[알고리즘] 프로그래머스 완주하지 못한 선수 자바 JAVA 해시 (0) | 2020.11.03 |
---|---|
[알고리즘] 프로그래머스 크레인 인형뽑기 게임 자바 JAVA 스택 (0) | 2020.11.03 |
[알고리즘] 백준 12865 자바 JAVA 동적프로그래밍 냅색 (0) | 2020.10.31 |
[알고리즘] 백준 11054 자바 JAVA 동적프로그래밍 LIS 최장 증가 수열 (0) | 2020.10.20 |
[알고리즘] 백준 11053 자바 JAVA 동적프로그래밍 LIS 최장 증가 수열 (0) | 2020.10.20 |