[프로그래머스] 시험장 나누기 / 2021 카카오 채용연계형 인턴십 - JAVA

🖇️ 문제 링크

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

카카오 인턴을 선발하는 코딩 테스트 시험장이 하나의 이진 트리 형태로 연결되어 있습니다. 아래 그림은 12개의 시험장이 연결된 예시입니다. 하나의 노드는 하나의 시험장을 나타냅니다. 검은 바탕의 흰 숫자는 해당 시험장의 고유 번호(ID)를 나타냅니다. 2-1. 시험장이 n개 있다면, 시험장의 고유 번호는 0부터 n-1까지 부여됩니다. 노드 안의 빨간 숫자는, 해당 시험장의 응시자 수를 나타냅니다.

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

 

---

📝 문제 분석

그리디, 최적화 결정 문제, 트리 등 복합적인 풀이가 필요한 문제였습니다.

 

k개의 그룹으로 나누었을 때, 최소화된 최대 그룹의 인원을 리턴해야 하는데 보통 이런 최적화 문제는 DP나 이분탐색을 사용하는 것 같습니다.

일단 문제를 모든 그룹을 L명 이하의 그룹으로 나누었을 때 K개 이하의 그룹으로 나눌 수 있는가? 하는 결정 문제로 바꿉니다. 이를 만족하는 최대의 L명을 구하는 것이 목표입니다.

 while(lo <= hi) {
    int mid = (lo + hi) / 2;
    if(getGroup(mid) <= k) {
      	hi = mid - 1;
    } else {
        lo = mid + 1;
    }
}

getGroup(mid) → mid명 이하로 그룹을 나누었을 때 몇 개의 그룹으로 나누어지는가

 

public int dfs(int curr, int limit) {
    int lv = 0, rv = 0;
    if(left[curr] != -1)
        lv = dfs(left[curr], limit);
    if(right[curr] != -1)
        rv = dfs(right[curr], limit);
    
    if(people[curr] + lv + rv <= limit)
        return people[curr] + lv + rv;
    
    if(people[curr] + Math.min(lv, rv) <= limit) {
        cnt++;
        return people[curr] + Math.min(lv, rv);
    }
   	
    cnt += 2;
    return people[curr];
}

그룹으로 나눌 때 세가지 경우가 존재합니다.

1. 루트, 왼쪽 서브트리, 오른쪽 서브트리 모두 한 그룹으로 묶기 → 그룹 + 0

2. 루트와 서브트리 한 곳만 그룹으로 묶기 → 그룹 + 1

3. 셋 다 다른 그룹으로 묶기 → 그룹 + 2

각각 그룹을 묶을 때, limit명 보다 크게 묶는 상황엔 그루핑 할 수 없습니다. dfs 한 번을 통해 밑에서부터 위로 그룹을 만들어나갑니다.

 

 

---

⌨️ 코드

import java.util.*;

class Solution {
    int n, root, cnt;
    int[] parent, left, right, people;
    
    public int solution(int k, int[] num, int[][] links) {
   		n = num.length;
       	parent = new int[n];
        left = new int[n];
        right = new int[n];
       	people = num;
        
        Arrays.fill(parent, -1);
        
        for(int i = 0; i < links.length; i++) {
            left[i] = links[i][0];
            right[i] = links[i][1];
            
            if(left[i] != -1)
           		parent[left[i]] = i;
            if(right[i] != -1)
            	parent[right[i]] = i;
        }
    	
       	for(int i = 0; i < n; i++)
            if(parent[i] == -1) {
                root = i;
                break;
            }
        
        int lo = 0, hi = (int) 1e9;
        for(int i = 0; i < n; i++)
            lo = Math.max(lo, people[i]);
        
        while(lo <= hi) {
            int mid = (lo + hi) / 2;
            if(getGroup(mid) <= k) {
              	hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        
        return hi + 1;
    }
    
    public int getGroup(int limit) {
       	cnt = 0; 
        dfs(root, limit);
        return cnt + 1;
    }
    
    public int dfs(int curr, int limit) {
        int lv = 0, rv = 0;
        if(left[curr] != -1)
            lv = dfs(left[curr], limit);
        if(right[curr] != -1)
            rv = dfs(right[curr], limit);
        
        if(people[curr] + lv + rv <= limit)
            return people[curr] + lv + rv;
        
        if(people[curr] + Math.min(lv, rv) <= limit) {
            cnt++;
            return people[curr] + Math.min(lv, rv);
        }
       	
        cnt += 2;
        return people[curr];
    }
}

 

 

 

 

Uploaded by Notion2Tistory v1.1.0