leetcode 2050, Parallel Courses 3

문제 설명

1부터 n개의 강의가 주어졌을 때, 해당 강의를 모두 듣는데 걸리는 최소 시간을 구하는 문제이다. 이때 어떤 강의는 선 수강 강의를 모두 들어야 들을 수 있다. 또한 강의를 들을 때는 특정한 시간이 소요된다고 하자.

https://leetcode.com/problems/parallel-courses-iii/description/

Parallel Courses III - LeetCode

문제 풀이

Topology sort를 이용하는 문제였다. 이때 조심해야 할 게 있는데, 노드들은 1부터 시작이지만 강의를 듣는 시간은 0부터 저장이 된다는 의미다. 즉, 노드 1의 시간은 time[0]에 저장되어 있다.

 

또한 최솟값을 구하라고 했지만, 우리는 각 degree의 최대 값을 구해줘야 한다. 그 이유는 간단한데, 코스1과 코스2가 각각 2달과 3달이 걸린다고 가정해보자. 이때 코스 3은 코스1과 코스2를 전부 수강해야지만 들을 수 있다. 그렇다면 코스1과 코스2를 겹쳐서 듣는다고 가정했을 때 걸리는 시간은 코스2의 시간인 3이다. 즉, 한 degree에 최대 값을 구해야 만 전체를 봤을 때 최솟값이 나오는 것이다.

 

일단 topology sort와 다를 바 없이 진행이 되지만, maxTime이라고 해서 각 코스마다 걸리는 최대값을 구하는 배열을 추가해줘야 한다.

 

일단 maxTime의 경우에는 0일 때 본래의 값을 넣어준다. 그리고 다음 노드를 확인해서 다음 노드의 선행 노드 갯수를 빼주는 반복문에서는 다음 노드의 maxTime을 갱신해준다. 이때 갱신하는 값은 기존의 값과 현재 노드의 최대 시간에다가 다음 노드의 시간을 더한 값을 비교해줘야 한다.

 

그리고 마지막으로 maxTime에서 최댓값을 반환해주면 된다. 맨 마지막 노드를 반환해주면 되지 않냐고 할 수도 있는데, 맨 마지막 노드가 마지막 degree의 노드라고 가정도 못할 뿐더러 마지막 노드가 2개 이상 나올 수 있기 때문에 반복문으로 최댓값을 찾아주는 거다.

코드

java

class Solution {

    public int minimumTime(int n, int[][] relations, int[] time) {
        List<List<Integer>> list = new ArrayList<>();
        int[] pre = new int[n+1];
        Queue<Integer> queue = new LinkedList<>();
        int answer = 0;
        int[] maxTime = new int[n+1];

        for (int i=0; i<=n; i++) {
            list.add(new ArrayList<>());
        }

        for (int i=0; i<relations.length; i++) {
            int a = relations[i][0];
            int b = relations[i][1];

            pre[b]++;
            list.get(a).add(b);
        }

        for (int i=1; i<=n; i++) {
            if (pre[i] == 0) {
                queue.add(i);
                maxTime[i] = time[i-1];
            }
        }

        while(!queue.isEmpty()) {
            int current = queue.poll();

            for (int nextNode : list.get(current)) {
                pre[nextNode]--;
                maxTime[nextNode] = Math.max(maxTime[nextNode], maxTime[current] + time[nextNode-1]);

                if (pre[nextNode] == 0) {
                    queue.add(nextNode);
                }
            }
        }

        for (int i=1; i<=n; i++) {
            answer = Math.max(answer, maxTime[i]);
        }

        return answer;
    }
}