참고 포스팅
📜 알고리즘 접근 방법
위 문제는 활동 선택 문제(Activity Selection problem) 이라고 합니다. 쉽게 설명하면 주어진 시간 내 최대한 할 수 있는 활동의 갯수를 묻는 문제입니다.
예를 들어, Expo의 박람회에 놀러간 경우 여러 활동들이 있다면, 각 활동들의 시작시간과 종료시간이 다릅니다. 최대한 박람회 운행 시간동안 많은 활동을 참여하고 싶은 경우 최적의 방식을 어떻게 구할까요?
Input : 활동들의 시작 시간과 종료 시간(si, fi)
*조건 : 종료 시간은 오름차순으로 정렬이 되어 있습니다.
표로 정리하면 다음과 같습니다.
3번 활동의 경우, 0분에 시작하여, 6분에 종료한다는 것을 의미합니다.
위에서 {i3, i9, i11} 를 선택한 경우가 있을 수 있습니다.
하지만, {i1, i4, i8, i11} 를 선택한다면 똑같은 시간에 더 많은 활동들을 참여할 수 있게 됩니다.
위와 같은 경우 해결 알고리즘은 그리디 알고리즘을 활용하여 구현이 가능합니다.
그리디 알고리즘의 특성은 매 순간 최선의 선택을 통해 최적의 해를 도출해내는 방식입니다. 즉, 현재 시간을 기준으로 가장 빠르게 끝나는 활동을 선택해야 많은 활동에 참여가 가능하게 되는 것입니다.
위 설명을 증명은 다음과 같습니다.
만약 활동1(i1)을 포함하지 않는 다른 최적의 해가 있다고 가정하겠습니다.
그 최적의 해는 최소 4초 이후에 끝나는 활동 하나를 수행했을 것입니다. 그런데 해당 활동은 활동1(i1)로 대체해도 동일한 결과를 가져올 것입니다.
결과적으로 현상황에서 선택할 수 있는 가장 빠른 활동을 선택하지 않는 경우의 수가 있다고 하더라도 그것은 빠른 활동을 선택한 경우로 대체가 가능하다는 것입니다.
💻 적용 방법
이를 구현하기 위해서는 서로 겹치지 않는 활동에 대해 종료시간이 빠르게 되면 더 많은 활동이 가능하다는 것을 기억하면 됩니다.
- 종료시간을 기준으로 오름차순 정렬.
만약, 종료 시간이 같은 경우 시작 시간을 기준으로 오름차순 정렬. - 이전 종료 시간과 다음 시작시간을 비교하여 크거나 같은 경우에 카운팅을 해줍니다.
- 현재 활동의 종료시간을 이전 종료 시간으로 초기화 해줍니다.
그런데, 왜 종료 시간이 같은 경우에 시작시간을 기준으로 오름차순 정렬을 해줘야 할까요?
예를 들어 설명하겠습니다. 다음과 같은 입력값이 들어왔다고 가정하겠습니다.
1 2, 7 8, 2 8종료시점을 기준으로만 정렬한 경우, 다음과 같이 정렬이 됩니다.
1 2
5 5
3 5이 때, 이전 종료 시간은 ' 2 ' 으로 초기화 되고, 다음으로 ' 5 ' 이라는 시작 시간과 비교하게 됩니다. 5는 2 이상의 수이기 때문에, 결과적으로 2번의 활동이 가능하다는 결론이 나오게 됩니다.
하지만 이는 정답이 아니게 됩니다. 실제 최적의 해는 {1 2, 3 5, 5 5}로 3번의 활동 횟수가 정답입니다. 이처럼 종료 시각이 같은 경우에 시작 시간을 기준으로 오름차순 정렬을 해주지 않았을 경우 위와 같은 오류로 인해 잘못된 값이 출력될 수 있습니다.
👾 성공
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] time = new int[n][2];
StringTokenizer st;
for(int i=0; i<n; i++){
st = new StringTokenizer(br.readLine());
time[i][0] = Integer.parseInt(st.nextToken());
time[i][1] = Integer.parseInt(st.nextToken());
}
br.close();
// 끝시간으로 정렬, 같은 경우 시작시간으로 정렬
Arrays.sort(time, new Comparator<int[]>(){
@Override
public int compare(int[] o1, int[] o2){
if(o1[1] == o2[1]){
return o1[0] - o2[0];
}
return o1[1] - o2[1];
}
});
int count = 0;
int prev_end_time = 0;
for(int i=0; i<n; i++){
if(prev_end_time <= time[i][0]){
prev_end_time = time[i][1];
count++;
}
}
System.out.println(count);
}
}