[프로그래머스][Java] 시험장 나누기 / 2021 카카오 개발자 인턴쉽

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오 인턴을 선발하는 코딩 테스트 시험장이 하나의 이진 트리1 형태로 연결되어 있습니다. 아래 그림은 12개의 시험장이 연결된 예시입니다.

1. 하나의 노드는 하나의 시험장을 나타냅니다.
2. 검은 바탕의 흰 숫자는 해당 시험장의 고유 번호(ID)를 나타냅니다.
3. 2-1. 시험장이 n개 있다면, 시험장의 고유 번호는 0부터 n-1까지 부여됩니다.
4. 노드 안의 빨간 숫자는, 해당 시험장의 응시자 수를 나타냅니다.
5. 3-1. 위의 그림에서, 9번 시험장에는 10명, 4번 시험장에는 8명, 6번 시험장에는 20명의 응시자가 시험을 볼 예정입니다.
6. 노드 사이의 간선은 해당 시험장이 연결되어 있음을 의미합니다.
7. 4-1. 위의 그림에서, 9번 시험장은 7번 시험장과, 7번 시험장은 6번 시험장과 연결되어 있습니다.

코딩 테스트를 총괄하는 무지는 안정적인 시험을 위해, 시험장에서 오는 트래픽을 k개의 그룹으로 나누어 각 그룹별 서버로 분산시키기로 하였습니다. 시험장 사이를 연결한 간선들 중 k-1개를 끊어서 시험장을 k 개의 그룹으로 나눌 계획입니다. 이때, 그룹별 최대 트래픽을 최소화하기 위하여 가장 큰 그룹의 인원을 최소화시켜야 합니다.

위의 그림에서 7번과 6번 시험장을 잇는 간선을 끊고, 9번과 7번 시험장을 잇는 간선을 끊는다면, 전체 시험장은 3개의 그룹으로 나누어집니다.

• 주황색 노드로 표시된 A그룹의 인원은 35명(10+8+5+6+1+1+4)
• 보라색 노드로 표시된 B그룹의 인원은 37명(7+30)
• 녹색 노드로 표시된 C그룹의 인원은 40명(20+8+12)

즉, 인원이 가장 많은 그룹은 40명입니다. 다른 어떤 방법으로 시험장을 3개의 그룹으로 나눈다고 해도, 인원이 가장 많은 그룹의 인원이 40명 미만이 되도록 나눌 수는 없습니다.

나눌 그룹의 수를 나타내는 정수 k, 각 시험장의 응시자 수를 나타내는 1차원 정수 배열 num, 시험장의 연결 상태를 나타내는 2차원 정수 배열 links가 매개변수로 주어집니다. 인원이 가장 많은 그룹의 인원이 최소화되도록 k개의 그룹으로 나누었을 때, 최소화된 최대 그룹의 인원을 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ k ≤ 10,000
• k ≤ num의 길이 ≤ 10,000
  • num[i]에는 i번 시험장의 응시자 수가 담겨있습니다.
  • 1 ≤ num의 원소 ≤ 10,000
• links의 길이 = num의 길이
  • links의 i번째 행은 i번 노드(시험장)의 [왼쪽 자식 노드 번호, 오른쪽 자식 노드 번호]입니다.
    • 해당 위치에 자식 노드가 없는 경우 -1이 담겨있습니다.
    • 잘못된 노드 번호나, 하나의 이진 트리 구조가 아닌 입력은 주어지지 않습니다.

정확성 테스트 케이스 제한 사항

• 1 ≤ k ≤ 20
• k ≤ num의 길이 ≤ 20

효율성 테스트 케이스 제한 사항

• 주어진 조건 외 추가 제한사항 없습니다.

---

입출력 예

k	num	links	result
3	[12, 30, 1, 8, 8, 6, 20, 7, 5, 10, 4, 1]	[[-1, -1], [-1, -1], [-1, -1], [-1, -1], [8, 5], [2, 10], [3, 0], [6, 1], [11, -1], [7, 4], [-1, -1], [-1, -1]]	40
1	[6, 9, 7, 5]	[[-1, -1], [-1, -1], [-1, 0], [2, 1]]	27
2	[6, 9, 7, 5]	[[-1, -1], [-1, -1], [-1, 0], [2, 1]]	14
4	[6, 9, 7, 5]	[[-1, -1], [-1, -1], [-1, 0], [2, 1]]	9

 

문제 풀이

이 문제를 처음 접하면 완전탐색으로 풀면 어떨까 라는 생각을 제일 많이할거라 생각합니다.

하지만 완전탐색을 할 경우 답은 나오겠지만 효율성에서 부족하다고 생각이 되어 최대 그룹의 인원 수를 기준으로 이분탐색으로 구현하였습니다.

 

low는 전체 트리 중 제일 큰 값이고 high는 (int)1e9입니다. 여기서 high를 Integer.parseInt로 선언하게 되면 low와 high를 더했을 때 integer 범위를 벗어나게 되므로 몇몇 테스트 케이스에서 실패가 뜨게 됩니다.

 

트리에서 그룹을 나누는 조건은 총 3가지 입니다.

1. 왼쪽 자식 + 오른쪽 자식 + 자신의 값 <= max 일 경우 간선을 자를 필요가 없습니다.

2. Math.min(왼쪽 자식, 오른쪽 자식) + 자신의 값 <= max일 경우 한쪽의 간선을 잘라야합니다. 

3. 둘 다 아닌 경우 두 개의 간선을 모두 잘라야 합니다. <- 여기서 low를 트리에서 제일 큰 값으로 지정한 이유가 나옵니다.

     ㄴ 만약 제일 작은 값을 기준으로 low를 잡게 되면 제일 작은 값이 1이고 맨 밑의 노드가 10일 때 처리할 수 없게 됩니다. 

 

위와 같이 조건을 잡으면 해결되는 문제이므로 level5보다는 쉽다고 생각이 되는 문제였습니다.

풀이 코드

import java.util.*;

class Solution {
    private int root, size;
    private Node[] tree;
    private int[] parent;
    
    public int solution(int k, int[] num, int[][] links) {
        int answer = 0;
        setTree(num, links);
        
        int low = 0, high = (int)1e9; 
        //high의 경우 Integer.MAX_VALUE를 하면 원소 중 최댓값을 더해줬을 때 
        //int범위를 벗어남으로 주의해줘야합니다.
        for(int n : num) low = Math.max(low, n);
        
        while(low <= high){
            int mid = (low+high)/2;
            if(checkGroup(num, mid) <= k){
                high = mid - 1;
            }else{
                low = mid + 1;
            }
        }
        return high+1;
    }
    
    private int checkGroup(int[] num, int max){
        size = 0; //자르는 개수
        dfs(num, root, max);
        return size+1;
    }
    
    private int dfs(int[] num, int cur, int max){
        int lv = 0, rv = 0;
        if(tree[cur].left != -1)
            lv = dfs(num, tree[cur].left, max);
        if(tree[cur].right != -1)
            rv = dfs(num, tree[cur].right, max);
        
        //자식 노드들과 자신의 값의 합이 max보다 작거나 같으면 자를 필요가 없다.
        if(num[cur] + lv + rv <= max) 
            return num[cur] + lv + rv;
        
        //자신 노드들 중 제일 작은 값과 자신의 값의 합이 max보다 작거나 같으면 한개만 자르면 된다.
        if(num[cur] + Math.min(lv, rv) <= max){
            size+=1;
            return num[cur] + Math.min(lv, rv);
        }
        
        //둘 다 잘라야하는 경우 
        //맨 밑단 노드 값이 max보다 작은 경우는 없습니다.
        //low가 제일 큰 노드를 기준으로 잡히기 때문에 무조건 첫번째 if에서 통과됩니다.
        size += 2;
        return num[cur];
    }
    
    private void setTree(int[] num, int[][] links){
        tree = new Node[num.length];
        parent = new int[num.length];
        
        Arrays.fill(parent, -1);
        
        for(int i=0; i<links.length; i++){
            tree[i] = new Node(links[i][0], links[i][1]);
            
            if(tree[i].left != -1) parent[tree[i].left] = i;
            if(tree[i].right != -1) parent[tree[i].right] = i;
        }
        
        for(int i=0; i<parent.length; i++){
            if(parent[i] == -1){
                root = i;
                break;
            }
        }
    }
    
    class Node{
        int left, right;
        
        public Node(int left, int right){
            this.left = left;
            this.right = right;
        }
    }
}

<출처>

https://programmers.co.kr/learn/courses/30/lessons/81305

코딩테스트 연습 - 시험장 나누기