프로그래머스 시험장 나누기 JAVA 풀이 (이분 탐색, DFS, 트리)

📌 문제 링크

프로그래머스

---

📌 문제 개요

여러 개의 시험장이 하나의 이진 트리 형태로 연결되어 있다.

각 시험장에는 응시자 수가 존재하며, 시험장 사이의 간선을 끊어 정확히 k개의 그룹으로 나누어야 한다.

 

각 그룹의 응시자 수 합을 계산했을 때,

가장 큰 그룹의 인원 수 를 최소화하는 것이 목표이다.

 

즉, 최대 그룹 인원 수의 최솟값 을 구하는 문제이다.

---

📌 접근 방법

처음에는 어떤 간선을 끊어야 하는지 직접 찾는 문제처럼 보인다.

하지만 시험장 수가 최대 10,000개이므로 모든 경우를 탐색하는 것은 불가능하다.

 

문제를 다시 보면, 최대 그룹 인원 수를 최소화 해야 한다.

 

이 문구를 보고 이분 탐색(Parametric Search)을 적용할 수 있다고 판단했다.

먼저 최대 그룹 인원 수를 limit라고 가정한다.

 

그 다음 DFS를 수행하면서 확인한다.

현재 limit 이하로 그룹을 나눌 수 있는가?

 

DFS 결과 필요한 그룹 수가

k 이하라면 더 작은 limit를 탐색하고,

k 초과라면 limit를 증가시키는 방식으로 정답을 찾는다.

---

📌 핵심 아이디어

1. 최대 그룹 인원 수를 이분 탐색한다

정답은 그룹 인원 수이므로 탐색 범위를 설정할 수 있다.

최소값은 단일 시험장 인원 중 최대값이다.

for (int n : num) {
    left = Math.max(left, n);
}

최대값은 모든 시험장의 응시자 수를 더한 값이다.

이 범위 안에서 최대 그룹 인원 수를 탐색한다.

for (int n : num) {
    right += n;
}

---

2. DFS로 필요한 그룹 수를 계산한다

현재 노드 기준으로 하나의 그룹으로 묶을 수 있는지 확인한다.

왼쪽 서브트리
오른쪽 서브트리
현재 노드

모두 포함 가능하다면 그룹을 유지한다.

if (left + right + num[cur] <= limit) {
    return left + right + num[cur];
}

예를 들어 아래와 같다면 하나의 그룹으로 유지할 수 있다.

현재 노드 = 5
왼쪽 합 = 10
오른쪽 합 = 15
limit = 40

10 + 15 + 5 = 30

---

3. 한쪽만 포함 가능한 경우

양쪽을 모두 포함할 수 없다면 더 작은 쪽만 유지한다.

if (Math.min(left, right) + num[cur] <= limit) {
    groupCount++;
    return Math.min(left, right) + num[cur];
}

예를 들어

• 오른쪽만 포함 왼쪽은 분리하게 된다.
• 이 경우 그룹 수가 1 증가한다.

현재 노드 = 5
왼쪽 합 = 30
오른쪽 합 = 10
limit = 20

 

---

4. 둘 다 포함할 수 없는 경우

현재 노드와 자식들을 모두 함께 유지할 수 없다면 양쪽을 모두 분리한다.

groupCount += 2;
return num[cur];

예를 들어 아래와 같다면, 양쪽 서브트리를 모두 분리해야 한다.

현재 노드 = 15
왼쪽 합 = 20
오른쪽 합 = 25
limit = 30

---

5. 루트 노드 직접 찾기

문제에서는 루트 노드가 주어지지 않는다.

따라서 자식으로 등장하지 않은 노드를 찾아야 한다.

boolean[] isChild = new boolean[num.length];

for (int[] link : links) {
    if (link[0] != -1) isChild[link[0]] = true;
    if (link[1] != -1) isChild[link[1]] = true;
}

자식으로 한 번도 등장하지 않은 노드가 루트가 된다.

---

📌 전체 코드

class Solution {

    int[] num;
    int[][] links;
    int k;
    int groupCount;

    public int solution(int k, int[] num, int[][] links) {
        this.num = num;
        this.links = links;
        this.k = k;

        int root = findRoot();

        int left = 0;
        int right = 0;

        for (int n : num) {
            left = Math.max(left, n);
            right += n;
        }

        int answer = right;

        while (left <= right) {
            int mid = (left + right) / 2;

            groupCount = 1;
            dfs(root, mid);

            if (groupCount <= k) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return answer;
    }

    int dfs(int cur, int limit) {
        if (cur == -1) return 0;

        int left = dfs(links[cur][0], limit);
        int right = dfs(links[cur][1], limit);

        if (left + right + num[cur] <= limit) {
            return left + right + num[cur];
        }

        if (Math.min(left, right) + num[cur] <= limit) {
            groupCount++;
            return Math.min(left, right) + num[cur];
        }

        groupCount += 2;
        return num[cur];
    }

    int findRoot() {
        boolean[] isChild = new boolean[num.length];

        for (int[] link : links) {
            if (link[0] != -1) isChild[link[0]] = true;
            if (link[1] != -1) isChild[link[1]] = true;
        }

        for (int i = 0; i < num.length; i++) {
            if (!isChild[i]) return i;
        }

        return -1;
    }
}

 

---

📄 정리

• 최대 그룹 인원 수의 최솟값을 구하는 문제이므로 이분 탐색을 적용할 수 있다.
• DFS 후위 순회를 이용해 현재 limit에서 필요한 그룹 수를 계산한다.
• 그룹 수가 k 이하이면 더 작은 limit를 탐색한다.
• 루트 노드가 주어지지 않으므로 직접 찾아야 한다.
• 트리 + DFS + Parametric Search가 결합된 카카오 고난도 문제