728x90
문제

제약조건

메모리 제약

입/출력

문제 분석
1. 강의 시작시간 : [강의 종료시간] 의 Map<Integer, int[]> 을 만든다.
2. 시작시간부터 쭉 따라가서 종료시간까지 가장 많은 depth를 거치는 경우를 선택한다.
풀이
import java.io.*;
import java.util.*;
public class Main {
static long maxTime = 0; // 최대 강의 시간
static long maxCount = 0; // 최대 강의 수
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
/*
3
1 3
2 4
3 5
*/
HashMap<Long, Set<Long>> lectureTimes = new HashMap<>();
long cnt = Long.parseLong(bf.readLine());
for (long i = 0; i < cnt; i++) {
long[] inputs = Arrays.stream(bf.readLine().split(" ")).mapToLong(Long::new).toArray();
if (lectureTimes.get(inputs[0]) == null) {
Set<Long> lists = new HashSet<>();
lists.add(inputs[1]);
lectureTimes.put(inputs[0], lists);
} else {
Set<Long> lists = lectureTimes.get(inputs[0]);
lists.add(inputs[1]);
lectureTimes.put(inputs[0], lists);
}
maxTime = inputs[1];
}
// 시작은 1부터
findCount(lectureTimes, 0, 1);
System.out.println(maxCount);
}
public static long findCount(HashMap<Long, Set<Long>> lectureTimes, long count, long findIdx) {
// 만약 강의 끝이면 종료
if (findIdx == maxTime ) {
return count;
}
// 마지막 시간이 없는 경우 종료
Set<Long> lists = lectureTimes.get(findIdx);
if (lists == null) {
return count;
}
for (long i : lists) {
long results = findCount(lectureTimes, count+1, i);
maxCount = Math.max(maxCount, results);
}
return count;
}
}
실패
메모리 초과/오답이 나왔다......
메모리 초과의 경우 모든 경우의 수를 다 방문하다보니 시간 복잡도가 O(2^N) 까지 늘어나게 된다...
오답의 경우 시작을 무조건 1에서 시작하는 방법만 있는 것은 아니다.
ex)
1 5
2 3
3 4
이렇게 주어지게되면 1을 고르는 것보다 2에서 시작하는게 더 많은 강의를 배정할 수 있다.

그래서 다른 로직을 생각해보았다.
강의를 많이 잡으려면 강의 종료 시간이 빠른 순서대로 정렬하여 시간을 계산하는건 어떨까?
1. 강의를 종료 시간 오름차순으로 정렬
2-1. 만약 다음 시작시간이, 이전 종료시간보다 빠르면 선택하지 않음 (이미 강의실을 사용중)
2-2. 만약 다음 시작시간이, 이전 종료시간보다 느리면 선택 (강의실 사용 가능)
풀이
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int cnt = Integer.parseInt(bf.readLine());
long[][] lectures = new long[cnt][2];
for (int i = 0; i < cnt; i++) {
String[] input = bf.readLine().split(" ");
lectures[i][0] = Long.parseLong(input[0]);
lectures[i][1] = Long.parseLong(input[1]);
}
// 종료 시간 기준으로 오름차순 정렬
Arrays.sort(lectures, Comparator.comparingLong(o -> o[1]));
int maxCount = 0; // 최대 강의 배정 수
long lastEndTime = 0; // 마지막 강의 시간
for (int i = 0; i < cnt; i++) {
// 현재 강의의 시작 시간이 마지막으로 배정된 강의의 종료 시간 이후라면
if (lectures[i][0] >= lastEndTime) {
lastEndTime = lectures[i][1]; // 이 강의를 선택
maxCount++;
}
}
System.out.println(maxCount);
}
}
성공

느낀점
간단한 알고리즘이지만, 너무 복잡하게 생각한 것 같다.
또한 이 문제의 핵심은 "종료시간 기준으로 오름차순 정렬을 한다" 인 것 같다.
알고리즘 분류
더보기
그리디
링크
https://softeer.ai/practice/6291
Softeer - 현대자동차그룹 SW인재확보플랫폼
softeer.ai
728x90
반응형
LIST
'Etc > 알고리즘' 카테고리의 다른 글
| [softeer] 6294 (0) | 2024.08.02 |
|---|---|
| [softeer] 9497 (0) | 2024.08.02 |
| [softeer] 6270 (0) | 2024.08.02 |
| [softeer] 6280 (1) | 2024.07.29 |
| [softeer] 9498 (0) | 2024.07.29 |