[프로그래머스][KAKAO_인턴][2021] 시험장 나누기

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

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

 

내가 작성한 코드

from collections import defaultdict, deque
import sys

sys.setrecursionlimit(10 ** 8)
class node:
    def __init__(self, v=0, parent=None, left=None, right=None):
        self.v = v
        self.parent = parent
        self.left = left
        self.right = right

def group(crnt, target):
    if crnt == None:
        return sys.maxsize, 0
    left_cost, left_group = group(crnt.left, target)
    right_cost, right_group = group(crnt.right, target)

    # merge all
    if left_cost + right_cost + crnt.v <= target:
        crnt_cost, crnt_group = left_cost + right_cost + crnt.v, left_group + right_group - 1

    # merge left
    elif left_cost < right_cost and left_cost + crnt.v <= target:
        crnt_cost, crnt_group = left_cost + crnt.v, left_group + right_group
    # merge right
    elif right_cost + crnt.v <= target:
        crnt_cost, crnt_group = right_cost + crnt.v, left_group + right_group

    # no merge
    else:
        crnt_cost, crnt_group = crnt.v, left_group + right_group + 1

    return crnt_cost, crnt_group


def is_possible_sum(root, target, k):
    return group(root, target)[1] <= k

def solution(k, num, links):
    N = len(num)
    nodes = defaultdict(node)
    for i, n in enumerate(num):
        nodes[i].v = n
        if links[i][0] != -1:
            nodes[i].left = nodes[links[i][0]]
            nodes[links[i][0]].parent = nodes[i]
        if links[i][1] != -1:
            nodes[i].right = nodes[links[i][1]]
            nodes[links[i][1]].parent = nodes[i]
    # search root
    root = None
    for i in range(N):
        if nodes[i].parent == None:
            root = nodes[i]

    l, r = max(num), sum(num)
    while l != r:
        mid = (r - l) // 2 + l
        if is_possible_sum(root, mid, k):
            r = mid
        elif mid == l:
            l = mid+1
        else:
            l = mid
    return l

• 트리 순회
  
  • 후위 순회로 서브트리의 합을 확인하여 특정값(target) 이하로 나뉘는 그룹 수 확인
• 파라메트릭 서치
  • 최적화 문제를 결정 문제로 바꾸는 방식
  • k 그룹의 최적 인원수를 구하는 문제를, 최대 인원을 대입하여 나오는 그룹수가 k 이상인지 확인하는 문제로 변형
  • 이진탐색 활용

 

다른 사람이 작성한 코드

// Javascript
function solution(k, num, links) {
    const tree = links.reduce((tree, v, i) => {
        tree[i] = {
            cost: num[i],
            l: v[0],
            r: v[1],
        };
        return tree;
    }, {});
 
    const n = num.length;
    const root = links.reduce((root, v) => {
        const [a, b] = v;
        if (a > 0) root -= a;
        if (b > 0) root -= b;
        return root;
    }, n * (n - 1) / 2);
 
    const go = limit => {
        const callStack = [root];
        const returnValues = {
            "-1": {
                cost: 0,
                cnt: 0,
            }
        };
        callStack.back = function () { return this[this.length - 1];};
        while (callStack.length) {
            const now = callStack.back()
                , {cost, l, r} = tree[now]
                , lRes = returnValues[l]
                , rRes = returnValues[r];
 
            if (!lRes) {
                callStack.push(l);
                continue;
            }
            if (!rRes) {
                callStack.push(r);
                continue;
            }
            callStack.pop();
 
            returnValues[now] = {
                cost,
                cnt: returnValues[l].cnt + returnValues[r].cnt,
            }
            const ret = returnValues[now];
 
            const underLimit = (...nodes) => {
                const sum = nodes.reduce((sum, v) => sum += v.cost, 0);
                return sum <= limit;
            }
 
            if (underLimit(ret, lRes, rRes)) {
                ret.cost += lRes.cost + rRes.cost;
            } else if (underLimit(ret, lRes) || underLimit(ret, rRes)) {
                ret.cost += Math.min(lRes.cost, rRes.cost);
                ret.cnt += 1;
            } else {
                ret.cnt += 2;
            }
        }
        return returnValues[root];
    };
 
    const getAnswer = () => {
        let l = Math.max(...num), r = 11111 * n;
        let ans = r;
        while (l <= r) {
            const m = Math.floor((l + r) / 2);
 
            if (go(m).cnt <= k - 1) {
                r = m - 1;
                ans = Math.min(ans, m);
            } else {
                l = m + 1;
            }
        }
        return ans;
    };
 
    return getAnswer();
}

• 코드는 javascript로 작성하셨다
• 아래 블로그에서 중요한 부분만 깔끔하게 정리해주셨다

 

https://degurii.tistory.com/231

[프로그래머스] 시험장 나누기 (Javascript, 2021 카카오 채용연계형 인턴십)

 

기억해야할 것

• 너무 풀고싶어서 시간을 매우 오래 사용했다
• 파라메트릭 서치 문제를 이전에도 본 적 있지만, 용어로 정의된 건 처음 봤다
  • 나는 이러한 문제 유형을 항상 그리디하게 접근하려해서 일부만 맞았었다
  • 비슷한 문제를 찾아서 풀어보고 적응해야겠다
  • 항상 유형을 헷갈리는 것도 문제지만, 막연하게 언젠가 유용할 느낌이 든다 ㅎㅎ