본 문제는 그리디 알고리즘을 사용하여 매 선택마다 최적의 답을 구하는 문제이다.
아래 블로그의 글을 참고하였다.
https://hongjw1938.tistory.com/172
시작 시간과 종료 시간을 가지고 있는 여러 회의들을 시간이 겹치기 않고 가장 많이 담을 때 총 개수를 구하는 문제이다.
핵심은
1. 다음 단계의 회의를 선택할 때 .조건은 전 회의 종료 시간보다 다음 단계의 회의 시작 시간이 늦거나 같아야 한다.
2. 다음 단계의 회의를 선택할 때 종료시간이 가장 짧은 회의를 선택하는 것의 최적의 답이다.
즉, 다음 단계의 회의를 선택할 때 (1) 전 회의의 종료 시간보다 다음 회의 시작 시간이 같거나 늦어야 하고 (2) 그 중에 종료 시간이 가장 짧은 회의를 선택해야 한다.
이를 위해 시작 시간과 종료 시간이라는 두 필드를 갖는 클래스를 생성했다.
그리고 이 클래스를 담고 있는 리스트를 종료 시간이 짧은 순으로 정렬하였다.
구현한 코드는 아래와 같다.
package com.yuk;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
public class No1931 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
ArrayList<Mt> list = new ArrayList<>();
while(N-- > 0) {
String[] strArr =br.readLine().split(" ");
int x = Integer.parseInt(strArr[0]);
int y = Integer.parseInt(strArr[1]);
list.add(new Mt(x,y));
}
list.sort(new Comparator<Mt>() {
@Override
public int compare(Mt o1, Mt o2) {
if(o1.y==o2.y) {
return o1.x-o2.x;
}
return o1.y-o2.y;
}
});
int cnt = 0;
int pre = 0;
while(true) {
int endTime = list.get(pre).y;
cnt++;
boolean flag = false;
for(int i=pre+1; i<list.size(); i++) {
if(list.get(i).x>=endTime) {
pre=i;
flag = true;
break;
}
}
if(!flag) break;
}
System.out.println(cnt);
}
}
class Mt {
int x;
int y;
public Mt(int x, int y) {
this.x = x;
this.y = y;
}
}
'Data Structure & Algorithm > 백준' 카테고리의 다른 글
No1260 DFS와 BFS(그래프 이론: 너비우선탐색, 깊이우선탐색) (0) | 2022.11.18 |
---|---|
No2630 색종이 만들기 (분할 정복) (0) | 2022.11.15 |
No1389 케빈 베이컨의 6단계 법칙(플로이드 와샬 알고리즘) (0) | 2022.11.02 |
Class2 돌파! (0) | 2022.10.27 |
No9012 괄호 (Stack) (0) | 2022.10.25 |