[프로그래머스] 시험장 나누기 (이분탐색)

ttps://school.programmers.co.kr/learn/courses/30/lessons/81305

프로그래머스

 

분석

 

인원이 가장 많은 그룹의 인원이 최소화되도록 k개의 그룹으로 나누었을 때, 최소화된 최대 그룹의 인원을 return

➔ 한 그룹당 몇명으로 잡아야 k개의 그룹으로 나눴을때 최대 인원인지 구하기

• 최대 노드 수: 10000개
• 그룹을 최대 몇 개까지 나눌 수 있는지: 10000개
• 완전 탐색 시: 조합(10000!) * 탐색(10000^2) ➔ 이분탐색

 

• k : 그룹의 수를 나타내는 정수
• num : 각 시험장의 응시자 수를 나타내는 1차원 정수 배열
• links : 시험장의 연결 상태를 나타내는 2차원 정수 배열 

k : 3
num : [12, 30, 1, 8, 8, 6, 20, 7, 5, 10, 4, 1],
links : [[-1, -1], [-1, -1], [-1, -1], [-1, -1], [8, 5], [2, 10], [3, 0], [6, 1], [11, -1], [7, 4], [-1, -1], [-1, -1]]

start	end	limit (mid)	그룹 수
30	112	71	3
30	71	50	3
30	50	40	3
30	40	35	4
36	40	38	4
39	40	39	4
40	40

answer = 40

 

 

풀이

import sys
sys.setrecursionlimit(10**6)

answer = 0

def solution(k, num, links):
    
    n = len(num)
    
    l = [0]*n
    r = [0]*n
    x = [0]*n
    
    parent=[-1]*n
    root=0
    
    for i in range(len(links)):
        x[i] = num[i]
        l[i], r[i] = links[i]
        if l[i] != -1: parent[l[i]] = i
        if r[i] != -1: parent[r[i]] = i

    for i in range(n): #  루트노드 찾기
        if parent[i]==-1:
            root=i; break
           
        
    def DFS(curr, limit):
        global answer
        left = right = 0
        if l[curr] != -1: left = DFS(l[curr], limit)
        if r[curr] != -1: right = DFS(r[curr], limit)

        # CASE 1: 모두 포함되는 경우
        if x[curr] + left + right <= limit:
            return x[curr] + left + right

        # CASE 2: limit보다 커서 한쪽 그룹을 자르는 경우
        if x[curr] + min(left, right) <= limit:
            answer += 1
            return x[curr] + min(left, right)

        # CASE 3: limit보다 커서 두쪽 그룹을 자르는 경우
        answer += 2
        return x[curr]

    
    def count(limit):
        global answer
        answer = 0
        DFS(root, limit)
        answer += 1
        return answer

    # 이분탐색
    start = max(x)
    end = sum(x)
    while start < end:
        mid = (start+end)//2
        if count(mid)<=k: # mid 명일 때
            end=mid
        else: 
            start=mid+1
        
    return start