[softeer] 6291

문제

 

 

제약조건

 

메모리 제약

 

입/출력

 

문제 분석

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인재확보플랫폼