그리디 알고리즘
종료 시간을 기준으로 정렬 -> 이전 종료시간에 대해 겹치는 것들은 제외하고 남은 것들 중 선택
빨리 끝나는 것 선택 : a1
a1을 선택한 뒤 다음으로 빨리 끝나는 것 a2 (a1과 겹치므로 제외), a3도 마찬가지
a4는 a1과 겹치지 않으면서 다음으로 빨리 끝남
-> 총 4개
import java.util.*;
import java.io.*;
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[][] meetingRoom = new int[N][2];
for(int i=0;i<N;i++){
StringTokenizer st = new StringTokenizer(br.readLine());
meetingRoom[i][0] = Integer.parseInt(st.nextToken());
meetingRoom[i][1]= Integer.parseInt(st.nextToken());
}
Arrays.sort(meetingRoom, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[1]==o2[1]){
return o1[0]-o2[1];
}
return o1[1]-o2[1];
}
});
int count = 0;
int prev_time= 0;
for(int i=0;i<N;i++){
if(prev_time<=meetingRoom[i][0]){
count++;
prev_time= meetingRoom[i][1];
}
}
System.out.print(count);
}
}
오늘의 회고
- 한 문제를 풀더라도 개념을 정확히 이해하고 풀자...
- 내일(4/9) 학습 예정 : 그리디 알고리즘 공부
'algorithm > 문제 풀이' 카테고리의 다른 글
99클럽 코테 스터디 10일차 TIL - 프로그래머스 이진 변환 반복하기 (0) | 2024.04.10 |
---|---|
99클럽 코테 스터디 9일차 TIL - 백준 1697번 (숨바꼭질) (0) | 2024.04.09 |
백준 1654번 (랜선 자르기) 자바 Java (0) | 2024.04.07 |
백준 10974번 (모든 순열) 자바 Java (0) | 2024.04.06 |
99클럽 코테 스터디 6일차 TIL - 프로그래머스 문자열 내 마음대로 정렬하기 (0) | 2024.04.06 |