[프로그래머스] 2021 카카오 인턴 #5 시험장 나누기 (Java)

#5 시험장 나누기

난이도 : LEVEL 5

유형 : 트리 dp / 파라메트릭 서치

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

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

programmers.co.kr

문제

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

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

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

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

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

문제 풀이

~~프로그래머스에서 처음으로 1등(java)을 찍어본다.~~ 개인적으로 5번은 풀이하기 어려웠다. 트리 dp는 다른 카카오 기출에도 나왔었기 때문에 어느정도 가닥은 잡았지만 dp배열에 담을 데이터를 정하고 어떻게 탐색을 이어나가야 되는지 해결을 하지 못하였다. 처음에 풀이할 때 가장 고민인 부분은 어떻게 케이스를 나누냐 이것이었는데 조합(comb)을 사용하여 모든 경우의 수를 구해주는 방법 외에는 다른 방법이 떠오르질 않았다.

ex) 20개의 노드가 주어지면 연결된 간선은 19개이다.

이때 k=4라면, 19개의 간선 중 3개를 끊어줘야 4개의 그룹이 나오므로 19C3의 경우를 뽑아줘야 한다.

→ 정확성 테스트 케이스는 k<=20, num <=20이었기 때문에 모든 조합을 뽑아서 탐색해줘도 통과한다.

그러나 효율성을 뚫기에는 k<=10,000 , num <=10,000 경우의 수가 너무 많았다. 카카오 해설을 참고해보니 이를 뚫기 위해서 필요한 개념이 파라메트릭 서치였다.

파라메트릭 서치

파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 풀어주는 방식으로 이진탐색과 유사하다.

	이진탐색	파라메트릭 서치
정의	정렬된 일련의 값들이 주어졌을 때 그 값들 중 원하는 값을 찾는 알고리즘	주어진 범위 내에서 원하는 값 또는 조건에 일치하는 값을 찾아내는 알고리즘
예시	1부터 9까지의 값에서 3이라는 값을 찾는다.	1~9범위 내에서 3이라는 값 또는 원하는 조건에 일치하는 값을 찾아가는 것

파라메트릭 서치는 이 문제와 같은 최적화 문제를 결정 문제로 바꾸어 푸는 데 사용된다.

주어진 최적화 문제: “트리를 k개 이하의 그룹으로 나누어서 얻을 수 있는 최소한의 최대 그룹의 크기는 얼마인가?”
변경된 결정 문제: “트리를 k개 이하의 그룹으로 나누어서 얻을 수 있는 최대 그룹의 크기가 L 이하가 되도록 할 수 있는가?”

트리를 k개 그룹을 나누었을 때, 최대 그룹의 가중치 합(L)이 (전체 가중치 합)/k보다는 작을 수 없기 때문에 L의 범위는 다음과 같다.

(전체 가중치 합) / k ≤ L ≤ (전체 가중치 합)

1번의 예제로 예시를 들면 (전체 가중치 합) = 112이고, k=3이다.

아무리 최대 그룹의 가중치 합을 최소로 만들려고 노드의 데이터를 구성해봐도 112/3 = (int)38이 최소이다.

해당 범위내에서 파라메트릭 서치를 해주면 된다.

int left = sum/k;
int right = sum;
while(left < right) {
	int mid = (left+right)/2;
	cost = new int[size][2];
	traversal(root, mid);
	if(cost[root][0] <= k) {
		right = mid;
	}else {
		left = mid+1;
	}
}

트리 DP

저번 기출과 마찬가지로 트리를 후위 순회하여 Bottom-up방식으로 리프노드부터 dp배열을 채워나갔다.

나는 처음에 dp[현재 노드][section사이즈]로 설정하여 풀이를 하는 바람에 제대로 꼬였었다. 최대 section사이즈가 1만이기 때문에 완전 잘못된 설계 방식이었다.

1. DP 데이터 설정

올바른 설계는 dp[현재 노드][0], dp[현재 노드][1] 이렇게 두 상태로 나눈 다음 각 공간에 적절한 데이터를 할당해주면 되었다.

dp[현재노드][0] : 현재 노드에 최대 그룹 인원(L)이하가 되도록 하기 위한 최소 section 크기를 저장하고,

dp[현재노드][1] : 최대 그룹 인원(L)이하가 되도록 하였을 때, 현재 노드를 포함한 서브 트리의 최솟값을 저장해주면 된다.

2. DP 값 할당

이제 dp에 넣은 데이터를 정했으니 이젠 경우의 수를 나눠 값을 할당해주면 되는데 경우는 총 4가지로 나눠진다.

1) 현재 노드 data + dp[l][1](왼쪽 자식 트리 최솟값) + dp[r][1](오른쪽 자식 트리 최솟값) <= L

왼쪽, 오른쪽 자식 트리들을 합쳐도 L값보다 작으면 해당 트리는 나눠줄 필요가 없다.

그룹(section)의 크기는 왼쪽 자식 트리 그룹, 오른쪽 자식 트리 그룹이 모두 현재 노드와 합쳐지는 것이므로 -1을 해준다.

2) 현재 노드 data + min(dp[l][1](왼쪽 자식 트리 최솟값), dp[r][1](오른쪽 자식 트리 최솟값)) <= L

1에 해당하지 않을 경우 한쪽만 껴줄 수는 없는지 고려해본다.

그룹(section)의 크기는 왼쪽 자식 트리 그룹 또는 오른쪽 자식 트리 그룹크기에 현재 노드가 포함되어지는 것이므로 따로 그룹의 크기가 증가하지는 않는다.

3) 현재 노드 data <= L

1,2에 해당하지 않을 경우, 양쪽 노드를 모두 잘라낸다.

그룹(section)의 크기는 원래 나눠져있던 왼쪽 자식 트리 그룹과 오른쪽 자식 트리 그룹크기에 현재 노드 그룹이 추가되었으므로 +1을 해준다.

4) 1,2,3에 해당하지 않을 경우 해당 트리는 L이하가 되도록 나눌 수 없다는 뜻이다.

그러면 해당 탐색의 DP데이터는 무의미하므로 INF값을 넣어줌으로써 L값을 높여서 다시 탐색해준다.

3. 서브트리 구조에 대한 경우의 수

모든 노드가 다 위의 그림과 같이 왼쪽, 오른쪽 자식트리를 갖고있는 것은 아니다. 이진트리에서 루트 노드를 기준으로 나올 수 있는 경우의 수는 총 3가지이다.

리프 노드인 경우 ( left == -1 && right == -1)
1. 리프 노드는 후위 순회에서 가장 처음으로 값을 할당받을 노드이므로 초기값을 설정해준다.
풀 노드인 경우 (풀 노드 : 왼쪽, 오른쪽 자식 노드가 모두 있는 경우로 정의) ( left != -1 && right != -1)
1. 왼쪽, 오른쪽 자식 트리가 존재한다면 위의 경우 그대로 진행해주면 된다.
2. 만약 리프노드의 데이터가 L값보다 크다면 해당 탐색은 불필요하므로 MAX값을 넣어준디.
왼쪽 자식 노드 혹은 오른쪽 자식 노드만 있는 경우 ( left != -1 && right == -1) || ( left == -1 && right != -1)
1. 한 쪽의 자식 노드만 존재하는 경우는 각 자식 노드의 경우만 고려해주면서 계산해주면 된다.

풀이 코드

서브트리 구조에 대한 경우의 수를 나눠준 다음 DP배열에 각 조건(4가지 경우)에 맞게 값을 할당해주면 된다. 마지막으로 탐색하는 right값이 최대 그룹의 크기 L이 된다. 케이스 나누는 코드는 어떻게 더 줄일 수도 있을 것 같은데 다음에 볼 때도 이해하기 쉽게 그냥 이대로 냅두려한다.

import java.util.ArrayList;
import java.util.List;
class Solution {
    static class Node{
		int data;
		int left, right;
		public Node(int data, int left, int right) {
			this.data = data;
			this.left = left;
			this.right = right;
		}
	}
    static int INF = 789654321, MAX_SECTION =10001;
    static List<Node>[] list;
    static int[][] cost;
    public int solution(int k, int[] num, int[][] links) {
        int size = num.length;
        list = new ArrayList[size];
        for(int i=0; i<size; i++) {
            list[i] = new ArrayList<>();
        }
        int sum = 0;
        boolean[] check = new boolean[size];
        for(int i=0; i<size; i++) {
            int left = links[i][0];
            int right = links[i][1];
            if(left != -1) check[left] = true;
            if(right != -1) check[right] = true;
            list[i].add(new Node(num[i], left, right));
            sum += num[i];
        }	

        int root = -1;
        for(int i=0; i<size; i++) {
            if(!check[i]) root = i;
        }

        int left = sum/k;
        int right = sum;
        if(left == right) return right;
        while(left < right) {
            int mid = (left+right)/2;
            cost = new int[size][2];
            traversal(root, mid);
            if(cost[root][0] <= k) {
                right = mid;
            }else {
                left = mid+1;
            }
        }
        return right;

    }

    static void traversal(int pos, int w) {
        Node curNode = list[pos].get(0);
        int data = curNode.data;
        int l = curNode.left;
        int r = curNode.right;

        if(l != -1) traversal(l,w);
        if(r != -1) traversal(r,w);
        // leaf 노드 
        if(l == -1 && r== -1) {
            if(data <= w) {
                cost[pos][0] = 1;
                cost[pos][1] = data;
            }else {
                cost[pos][0] = MAX_SECTION;
                cost[pos][1] = INF;
            }
        }
        // full 노드 
        else if(l!=-1&&r!=-1){
            // 1) pos + 왼쪽 트리 + 오른쪽 트리 <= L 
            // section l+r-1
            if(data + cost[l][1] + cost[r][1] <=w) {
                cost[pos][0] = cost[l][0] + cost[r][0] -1;
                cost[pos][1] = data + cost[l][1] + cost[r][1];
            }
            // 2) pos + min(왼쪽, 오른쪽)  <= L
            // section  l+r
            else if(data + Math.min(cost[l][1],cost[r][1]) <= w) {
                cost[pos][0] = cost[l][0] + cost[r][0];
                cost[pos][1] = data + Math.min(cost[l][1], cost[r][1]);
            }
            // 3) pos <= L
            // section  l+r +1
            else if(data <= w) {
                cost[pos][0] = cost[l][0] + cost[r][0] +1;
                cost[pos][1] = data;
            }
            else {
                cost[pos][0] = MAX_SECTION;
                cost[pos][1] = INF;
            }
        }else {
            // 왼쪽 자식만 있는 경우
            if(r == -1) {
                // 1) pos + 왼쪽 트리 <= L
                // section l 
                if(data + cost[l][1] <=w) {
                    cost[pos][0] = cost[l][0];
                    cost[pos][1] = data + cost[l][1];
                }
                // 1) pos <= L
                // section l +1  
                else if(data <= w) {
                    cost[pos][0] = cost[l][0]+1;
                    cost[pos][1] = data;
                }
                else {
                    cost[pos][0] = MAX_SECTION;
                    cost[pos][1] = INF;
                }
            }

            // 오른쪽 자식만 있는 경우
            if(l == -1) {
                // 1) pos + 오른쪽 트리 <= L
                // section r 
                if(data + cost[r][1] <=w) {
                    cost[pos][0] = cost[r][0];
                    cost[pos][1] = data + cost[r][1];
                }
                // 1) pos <= L
                // section r +1  
                else if(data <= w) {
                    cost[pos][0] = cost[r][0]+1;
                    cost[pos][1] = data;
                }
                else {
                    cost[pos][0] = MAX_SECTION;
                    cost[pos][1] = INF;
                }
            }
        }
    }
}

'Dot Algo∙ DS > PS' 카테고리의 다른 글

[BOJ] 백준 1194번 달이 차오른다, 가자 (Java) (0)	2021.07.25
[BOJ] 백준 1062번 가르침 (Java) (0)	2021.07.25
[프로그래머스] 2021 카카오 인턴 #4 미로 탈출 (Java) (0)	2021.07.21
[프로그래머스] 2021 카카오 인턴 #3 표 편집 (Java) (0)	2021.07.19
[프로그래머스] 2021 카카오 인턴 #2 거리두기 확인하기 (Java) (0)	2021.07.18

일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

그릿 속의 해빗

[프로그래머스] 2021 카카오 인턴 #5 시험장 나누기 (Java)