문제

(2023 KAKAO BLIND RECRUITMENT 1차 코딩 테스트 마지막 문제)

풀이

완전 탐색으로 풀었다간 시간초과가 날 것이 뻔하므로 일단 문제에 숨어있는 원리를 찾아보려 고민했다. 결국 모든 수는 리프 노드에 들어가므로 중간 과정은 생각할 필요가 없고, 탐색 순서에 따라 호출되는 리프 노드의 리스트를 따로 저장해 둔다면 탐색에 시간을 낭비하지 않을 수 있다. "길"은 자식 노드의 수를 주기로 순환하며, 이는 자식을 따라 내려가면서 누적으로 곱해진다. 결국 리프 노드의 호출 주기는 형제의 수를 누적해서 곱한 값이 되며, 전체 리프 노드 주기의 최소공배수를 주기로 리프 노드 호출이 반복될 것이다.

예시 트리에 대입해서 설명하면, 노드 2와 노드 3은 주기 2로 순환한다. 노드 4와 노드 5는 노드 2가 호출될 때마다 주기 2로 순환하므로 주기 4로 순환하게 된다. 주기 4인 리프 노드와 주기 6인 리프 노드가 있으므로 전체 주기는 12이다.

'무슨 수'를 넣을지를 결정하기 전에 수를 '몇 개' 넣을지부터 결정할 수 있다. 수는 1, 2, 3 중 하나이므로 수가 $n$개 들어간 리프 노드는 $n$ 이상 $3n$ 이하의 값을 가질 수 있고, 이 범위에 target[i]이 들어간다면 목표치를 달성할 수 있다. 반대로 수를 하나씩 넣는 과정에서 하나라도 범위를 벗어난다면 목표치를 만들 수 없다. 수를 하나씩 넣으면서 최로로 목표를 달성할 수 있는 순간을 포착하면 수의 개수가 최소가 되며, 개수의 합이 전체 목표치의 합보다 커지면 더 이상 만들 수 없다는 뜻이다.

수의 개수를 결정하고 나면 1, 2, 3을 몇 개씩 넣을지는 그리디 알고리즘으로 결정할 수 있다. 사전식으로 배열하라 했으므로 1, 2, 3 순서로 넣으면 된다.

코드

import math
from collections import deque


def solution(edges, target):
    # math.lcm 은 파이썬 3.9부터 이용 가능
    def lcm(array):
        if len(array) == 1:
            return array[0]
        mid = len(array) // 2
        l = lcm(array[:mid])
        r = lcm(array[mid:])
        return l * r // math.gcd(l, r)

	# 루트 노드에서 "길"을 바꿔가며 도착한 노드를 반환
    def search(graph):
        start = 1
        while graph[start]:
            nxt = graph[start].pop(0)
            graph[start].append(nxt)
            start = nxt
        return start

	# 입력받은 간선으로부터 트리 만들기
    N = len(target)
    graph = {i: [] for i in range(N + 1)}
    for s, e in edges:
        graph[s].append(e)
    for i in range(N + 1):
        graph[i].sort()

	# 자식을 따라 가며 형제 수의 누적곱이 주기
    period = [1] * (N + 1)
    q = deque([[1, 1]])
    while q:
        parent, product = q.popleft()
        period[parent] = product
        if graph[parent]:
            product *= len(graph[parent])
            for child in graph[parent]:
                q.append([child, product])
    # 각 주기의 최소공배수가 전체 주기
    period[0] = lcm(period)

	# 리프 노드 방문 순서를 저장하기 위해 주기만큼 순회
    order = []
    for i in range(period[0]):
        order.append(search(graph))

	# 삽입 횟수를 저장하는 리스트
    check = [0] * (N + 1)
    index = 0
    while not all([check[i] <= target[i - 1] <= check[i] * 3 for i in range(1, N + 1)]):
        check[order[index]] += 1
        index = (index + 1) % period[0]
        # 만들 수 없는 경우 즉시 탈출
        if sum(check) > sum(target):
            return [-1]

	# 삽입할 수를 저장하는 딕셔너리
    answer = {}
    for i in range(1, N + 1):
        if target[i - 1] == 0:
            continue
        # 개수가 최소가 되는 사전순으로 가장 먼저 오는 케이스 = 그리디
        three = (target[i - 1] - check[i]) // 2
        two = (target[i - 1] - check[i]) % 2
        one = check[i] - two - three
        answer[i] = [1] * one + [2] * two + [3] * three

	# 리프 노드 방문 순서대로 결과 배열에 옮겨서 저장
    procedure = []
    for i in range(sum(check)):
        procedure.append(answer[order[i % period[0]]].pop(0))

    return procedure

사족

역시 카카오 마지막 문제라 그런지 코드가 꽤나 길었다. 프로그래머스 사이트에는 레벨 4로 올라와있다. 구현, 탐색, 그리디 알고리즘이 복합적으로 이용되는 문제라서 구현 아이디어를 떠올리는 과정이 특히 중요했던 것 같다.

math.gcd()는 3.5 버전, math.lcm()은 3.9 버전부터 이용할 수 있는데, 프로그래머스 컴파일러는 파이썬 버전이 3.8.5라서 lcm()은 직접 구현해야 했다.

노드 번호는 1부터 시작하는데 target 리스트는 0부터 시작이라서 인덱스 일치시키는 게 좀 헷갈렸다. 앞에 무의미한 값을 하나 넣어서 한 칸씩 밀면 간단히 해결되긴 했겠지만 입력으로 들어오는 값은 웬만하면 직접 건드리고 싶지 않아서 그대로 두었다.
(제출하고 알게 되었는데 효율성 테스트가 없어서 한 칸 밀어서 복사하는 방법도 생각해 볼 수 있었겠다.)