JS Coding Blog

선행 과목을 지키며 끝내는 최소 학기 수

자바스크립트 코딩테스트 문제로 topological-sort 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

algorithm medium topological-sort 함수명: solution 제한 시간: 300ms

과목 수와 선수 과목 정보가 주어질 때, 모든 과목을 끝내기 위해 필요한 최소 학기 수를 구하는 문제입니다.

문제 설명

1번부터 n번까지의 과목이 있습니다. prerequisites[i] = [a, b]는 과목 a를 먼저 이수해야 과목 b를 들을 수 있다는 뜻입니다.

한 학기에는 그 학기가 시작될 때 이미 선수 조건을 모두 만족한 과목들만 동시에 원하는 만큼 들을 수 있습니다.

모든 과목을 끝낼 수 있다면 필요한 최소 학기 수를 반환하고, 선수 조건이 서로 꼬여 있어서 불가능하다면 -1을 반환하세요.

제한사항

  • 1 <= n <= 200,000
  • 0 <= prerequisites.length <= 300,000
  • prerequisites[i] = [a, b]
  • 1 <= a, b <= n
  • a !== b
  • 같은 선수 조건이 여러 번 주어지지 않습니다.
  • 반환값은 모든 과목 이수에 필요한 최소 학기 수 또는 -1입니다.

예시

  • 입력: n = 4, prerequisites = [[1, 3], [2, 3], [3, 4]] → 출력: 3
    • 1학기: 1, 2
    • 2학기: 3
    • 3학기: 4
  • 입력: n = 5, prerequisites = [[1, 4], [2, 4], [4, 5]] → 출력: 3
    • 1학기에는 1, 2, 3을 들을 수 있습니다.
    • 2학기에는 선수 조건이 풀린 4
    • 3학기에는 5
  • 입력: n = 3, prerequisites = [[1, 2], [2, 3], [3, 1]] → 출력: -1
    • 서로가 서로의 선수 과목이어서 시작 가능한 과목이 없습니다.

힌트

  • 선수 과목이 하나도 없는 과목부터 시작해야 합니다.
  • 각 과목이 아직 남아 있는 선수 과목 수를 세어 두면, 다음에 들을 수 있는 과목이 언제 생기는지 알 수 있습니다.
  • 이번 학기에 들을 과목 묶음과 다음 학기에 새로 열리는 과목 묶음을 섞으면 학기 수를 잘못 셀 수 있습니다.

해설

이 문제는 그래프에서 위상 정렬(topological sort) 감각을 익히기 좋은 문제입니다.

과목을 정점, 선수 조건 a -> b를 방향 간선이라고 보면, 어떤 과목을 들으려면 그 과목으로 들어오는 간선이 모두 먼저 처리되어야 합니다.

1. 진입 차수 세기

각 과목에 대해 indegree[x]를 아직 남아 있는 선수 과목 수라고 생각합니다.

  • a -> b가 있으면 indegree[b] += 1
  • 처음부터 indegree가 0인 과목은 바로 들을 수 있습니다.

이 과목들을 큐에 넣고 시작합니다.

2. 한 학기 단위로 묶어서 처리하기

중요한 점은 같은 학기 안에서는 새로 열린 과목을 바로 듣지 못한다는 것입니다.

예를 들어 이번 학기에 과목 1을 들었다고 해서, 1을 선수로 필요로 하던 과목을 같은 학기에 곧바로 들을 수는 없습니다. 그 과목은 다음 학기에만 들을 수 있습니다.

그래서 큐를 그냥 끝까지 비우는 것이 아니라, 매 학기마다:

  1. 현재 큐에 들어 있는 과목 개수를 먼저 기록하고
  2. 그 개수만큼만 꺼내 이번 학기 과목으로 처리한 뒤
  3. 처리 과정에서 새로 indegree가 0이 된 과목은 큐 뒤에 넣고
  4. 다음 반복에서 다음 학기로 세면 됩니다.

이렇게 하면 레벨(level) 단위 BFS처럼 학기 수를 정확히 셀 수 있습니다.

3. 사이클 판별

모든 과목을 다 처리하지 못했다면, 어딘가에 사이클이 있다는 뜻입니다.

예를 들어 1 -> 2 -> 3 -> 1처럼 서로가 서로의 선수 조건이면, 처음부터 진입 차수 0인 과목이 하나도 없어서 시작조차 할 수 없습니다.

따라서:

  • 처리한 과목 수가 n과 같으면 학기 수 반환
  • 다르면 -1 반환

4. 왜 최소 학기 수일까?

각 학기마다 지금 당장 들을 수 있는 과목을 전부 듣는 것이 가장 빠릅니다. 어차피 선수 조건이 풀리지 않은 과목은 못 듣고, 들을 수 있는 과목을 미루면 전체 일정만 늦어집니다.

즉, 위상 정렬을 학기 단위 레벨로 처리한 결과가 곧 최소 학기 수입니다.

5. 시간 복잡도

  • 각 과목은 큐에 최대 한 번 들어갑니다.
  • 각 선수 조건 간선도 정확히 한 번만 확인합니다.

따라서 시간 복잡도는 O(n + prerequisites.length)이고, 추가 공간도 인접 리스트와 진입 차수 배열 때문에 O(n + prerequisites.length)입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.