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

[프로그래머스][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

기억해야할 것

너무 풀고싶어서 시간을 매우 오래 사용했다

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

from http://pythaac.tistory.com/236 by ccl(A) rewrite - 2021-09-05 19:26:59