2023 KAKAO BLIND RECRUITMENT 1,2,3 떨어트리기

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/150364

파이썬 소스: https://bit.ly/49zW8MP

 

 문제의 설명이 꽤 긴 문제여서, 읽기 좀 부담 되기는 하는 대요, 간단히 요약하면, 트리의 루트노드부터 리프노드까지 문제에서 주어진 규칙에 따라서, 숫자를 하나씩 보내는 문제입니다. 루트노드는 트리의 제일 위에 있는 노드를 말하구요, 리프노드는 자식이 없는 트리의 제일 하단 부에 위치하는 노드를 말합니다.

리프노드에 쌓인 숫자들을 가지고, target값이 될 수 있는지 판단도 해야 하지만, 우선은 트리안에서 1,2,3 숫자가 지나가는 방법부터 알아보겠습니다.

 트리부터 만들어야 하구요, 트리를 만들려면, 노드가 필요합니다.

class Node:     def __init__(self, node_num, target):         self.num = node_num         self.children: List[Optional[Node]] = []         self.target = target         self.idx_child = 0         self.indexes123: List[int] = []

 

self.num 은 edges에서 주어지는, 부모 노드 번호 or 자식 노드 번호 둘중의 하나입니다.

self.children은 이 노드의 자식 노드들을 리스트로 가지고 있습니다.

self.target은 solution함수의 target[self.num -1] 한 값입니다. 꼭 노드안에 target값을 넣어 둘 필요는 없지만, 코딩할 때 코드를 좀 단순하게 하기 위해서, self.target이 필요합니다.

self.idx_child는 1, 2, 3숫자를 부모 노드에서 자식 노드로 보낼 때, 여러 개의 자식 노드 중에서 어떤 자식 노드로 보낼지 가리키는 변수입니다.

self.indexes123는 int값을 가지는 리스트로, 루트 노드 보내지는, 아직은 1 or 2 or 3 이 될지 모르지만, 해당 숫자가 정해지면, 그 순서의 위치를 가리키는 인덱스 입니다.

어떤 리프 노드의 target 값이 3 이고, indexes123[0, 3] 이라고 한다면, 해당 리프노드에서 1, 2, 3중에 2개의 숫자를 사용해서 3을 만들어야 합니다. [1, 2]로 target인 3을 만들 수 있구요, solution()함수가 리턴할 답에 0, 3번 위치에는 1, 2가 들어가야 합니다.

[1, ?, ?, 2, … … …] <- 이렇게 1, 과 2가, 리스트의 0번, 3번에 위치해야 합니다. target값을 계산하는 방법은 이 후에 좀더 설명하도록 하겠습니다.

 문제풀이의 시작인 solution() 함수 입니다.

def solution(edges: List[List[int]], target: List[int]):     nodes = defaultdict(lambda : None)

트리에 들어갈 노드를 저장할 때, defaultdict()를 사용해서 기본값을 None으로 설정하고, 노드의 번호가 주어졌을 때, None이면 아래와 같이 Node를 만들어 줍니다. 노드를 저장하는대 딕셔너리를 사용하면, node를 꼭 필요한 만큼만 만들 수 있습니다. 만약에 nodes변수를 리스트로 만들면, 최대 노드 개수인 100개를 모두 None으로 만들어 놓고, 노드를 만들어야 합니다.

for parent_num, child_num in edges:         if nodes[parent_num] is None:             nodes[parent_num] = Node(parent_num, target[parent_num - 1])         if nodes[child_num] is None:             nodes[child_num] = Node(child_num, target[child_num - 1])

리스트 edges의 한 원소는 부모 노드 번호, 자식 노드 번호로 구성되어 있습니다. 어떤 노드 번호이든 한번 Node()를 만들 어 두면, 해당 노드 번호는 None이 아니기 때문에, 중복해서 노드를 만들지 않습니다.

nodes[parent_num].children.append(nodes[child_num])

부모노드에 자식노드를 넣어 줍니다.

leaves: List[Node] = []

리프노드에만 1, 2, 3이 쌓이기 때문에, 리프노드만 저장할 리스트를 만들어 줍니다. 이후에 leaves에 저장되어 있는 노드들만 사용해서, 1, 2, 3을 사용해 target 값을 만들 것입니다.

for node_num in nodes.keys():         if len(nodes[node_num].children) > 0:             nodes[node_num].children.sort()         else:             leaves.append(nodes[node_num])

만들어진 모든 노드 들은 2가지로 분류할 수 있습니다. 자식 노드가 있는 노드이거나, 자식 노드가 없는 리프 노드입니다. 여기서, children.sort()하는 것을 주의 깊게 봐주세요. 문제에서는 아래와 같은 문구가 있습니다.

모든 부모 노드는 자신의 자식 노드 중 가장 번호가 작은 노드를 가리키는 간선을 초기 길로 설정합니다. … … … 숫자가 리프 노드에 도착하면, 숫자가 지나간 각 노드는 현재 길로 연결된 자식 노드 다음으로 번호가 큰 자식 노드를 가리키는 간선을 새로운 길로 설정하고 기존의 길은 끊습니다.

처음으로 1, 2, 3을 보낼 노드는 자식 노드 중에서 번호가 가장 작은 노드 이며, 한번 보낼 때 마다 이전에 1, 2, 3을 보낸 노드 보다, 다음으로 번호가 큰 자식 노드에 1, 2, 3을 보내야 합니다.

리스트 edges에 들어 있는 보모 노드 번호와, 자식 노드 번호의 순서는 위의 문제 조건을 만족하지 않습니다. 따라서, 자식 노드를 가지고 있는 부모 노드는 sort()를 해야 합니다.

 여기서, children은 Node의 객체를 가지고 있는 리스트 인대… 어떻게 sort()를 사용할 수 있지? 라는 의문이 들 수 있습니다. __lt__ 메서드를 아래와 같이 Node 클래스가 구현하고 있으면, children리스트에서 sort()를 사용할 수 있습니다.

def __lt__(self, other): return self.num < other.num

 

이제 루트 노드에서 1, 2, 3을 보낼 차례입니다.

idx123 = 0     while True:         if False == nodes[1].send_num123(idx123):             return [-1]

1, 2, 3을 보낸다고 하지만, 사실은 solution()함수가 리턴 할 답 리스트의 X번 위치를 리프노드로 보내는 것입니다.  코드에서 send_num123()메서드가 False를 리턴하면 특정 리포노드가 리프노드에 해당하는 target값을 1, 2, 3을 사용해서 만들 수 없다는 뜻입니다. 따라서, [-1]을 리턴합니다.

 send_num123()메서드는 아래와 같이 코딩되어 있습니다.

def send_num123(self, idx123):         if len(self.children) == 0:             self.indexes123.append(idx123)             return not len(self.indexes123) > self.target         rtn = self.children[self.idx_child].send_num123(idx123)         self.idx_child = (self.idx_child + 1) % len(self.children)         return rtn

self.children의 길이가 0이면 즉, 리프 노드 이면, idx123을 indexes123에 넣어서, 나중에 self.target을 1, 2, 3을 사용해서 만들 때 사용합니다. 단 self.indexes123의 길이가 self.target보다 크다면, 1, 2, 3을 사용해서 target을 만들 수 없습니다. 1, 2, 3중에 가장 작은 숫자인 1만 사용해도, self.target값 보다 커지기 때문입니다. 여기서는 현재 indexes123의 길이로 만들 수 있는 최대 값보다, target이 큰 아래 경우는 고려하지 않아도 됩니다. 왜냐하면, idx123을 더 받아서, indexes123의 길이는 더 커질 수 있기 때문입니다.

len(self.indexes123) < self.target

 메서드 send_num123()을 재귀적으로 호출해서, 리프노드까지 idx123을 보내줍니다.

이 노드에 3개의 자식 노드가 있다고 가정할 때, idx_child는 0인 상태 입니다.

첫번째로 메서드 send_num123()이 호출되면, children[0] 에게 idx123을 보내고, idx_child는 1이 됩니다.

두번째로 메서드 send_num123()이 호출되면, children[1] 에게 idx123을 보내고, idx_child는 2이 됩니다.

두번째로 메서드 send_num123()이 호출되면, children[2] 에게 idx123을 보내고, idx_child는 3이 됩니다. 여기서 % 3 한 나머지를 저장하기 때문에, idx_child는 다시 0으로 되돌아 갑니다.

idx123 = 0     while True:         if False == nodes[1].send_num123(idx123):             return [-1]         idx123 += 1         if num123_make_target(leaves):             break

위와 같이 루트노드 nodes[1]에서 send_num123()을 호출 하구요, False가 리턴되지 않는 한 계속 해서 idx123은 1씩 증가한 값을 보내게 됩니다. num123_make_target()함수는 인자로 leaves 리스트를 받습니다. leaves에는 리프노드들만 들어 있습니다. 이 함수는 모든 리프 노드들이 각 리프 노드들에게 주어진 target값을 만들수 있는지 확인하는 함수 입니다.

def num123_make_target(leaves):     for idx in range(len(leaves)):         if not len(leaves[idx].indexes123) <= leaves[idx].target <= len(leaves[idx].indexes123) * 3:             return False     return True

indexes123의 길이는 target값을 만들 때, 1, 2, 3 을 몇 번 사용할 수 있는지를 의미 합니다.

Indexes123의 길이에 따라서, 만들 수 있는 최소 target값과, 최대 target값이 변하게 됩니다.

만들 수 있는 최소 target 값 : len(leaves[idx].indexes123)

만들 수 있는 최대 target 값 : len(leaves[idx].indexes123) * 3

위의 2개 값의 범위 안에 target값이 존재하면, 1, 2, 3을 len(indexes123) 만큼 사용해서, target을 만들 수 있습니다. 모든 리프 노드가 각 노드에 주어진 target값을 만들 수 있으면, True를 리턴해서, while 루프가 종료됩니다.

 

Idx123변수에는 모든 리프노드가 1, 2, 3을 선택할 수 있는 횟수가 들어 있습니다. 따라서, 답으로 리턴할 answer 리스트의 길이는 idx123이어야 합니다.

answer = [0] * idx123

0이 1개 들어 있는 리스트에 idx123을 곱해서, idx123길이 만큼 0을 가진 리스트로 만들어 줍니다.

for leaf in leaves:         ans = make_target_from123(len(leaf.indexes123), target[leaf.num - 1])

각 leaf 노드마다 방문해서, 아래 조건에 해당하는 1, 2, 3을 원소로 하는 리스트를 만들 차례 입니다.

리스트의 길이는 : len(leaf.indexes123)

리스트에는 1, 2, 3만 원소로 들어갈 수 있음

리스트의 모든 원소의 합은 target[leaf.num - 1] 같아야 함

여기서, make_target_from123()함수를 사용할 때, 재귀적인 방법으로도, 원하는 리스트를 구할 수 있는 있습니다. 하지만, 재귀적인 방법으로 시도하면, 여기서 시간 초과가 발생할 수 있습니다.

최악의 경우에는 O(3 ** 100) 정도 되는 연산량입니다. 물론 중간에 합을 구해서, 조금 더 빨리 재귀를 나오게 할 수도 있겠지만, 3 ** 20 만해도, 3,486,784,401 대략 3 * 10**9 이 넘는 숫자입니다.

 문제의 아래 부분에서 아이디어를 얻어서 조금 빠른 방법으로 원하는 1, 2, 3으로 구성된 리스트를 구할 수 있습니다.

target 대로 리프 노드에 쌓인 숫자의 합을 맞추기 위해 숫자를 떨어트리는 모든 경우 중 가장 적은 숫자를 사용하며 그중 사전 순으로 가장 빠른 경우를 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 가장 적은 숫자를 사용하라고 문제에 적혀 있지만, 우리가 사용해야 할 1, 2, 3 숫자의 개수는 len(self.indexes123) 입니다. 중요한 건 ‘사전 순으로 가장 빠른 경우’ 이 문장에서 힌트를 얻어야 합니다. 6을 1, 2, 3중에서 4번 선택해서 만드는 방법에는 1113 1122 2가지 경우가 있습니다.

이 두가지 중에 사전 순으로 빠른 방법은 1113 입니다. 즉 1, 2, 3중에서 최대한 3을 사용해서 target 값을 만들고, 3을 사용할 수 없다면 2를 사용하고, 마지막에 1을 사용해서 target 값을 만들어야 합니다.

앞에서, 아래 식이 성립하면, target 값을 구 할 수 있다고 설명했습니다.

len(leaves[idx].indexes123) <= leaves[idx].target <= len(leaves[idx].indexes123) * 3

그러면 여기서 3을 먼저 선택합니다. target 값은 3이 줄고, indexes123의 길이는 1감소 합니다.

len(leaves[idx].indexes123) -1 <= leaves[idx].target -3 <= (len(leaves[idx].indexes123)-1) * 3

위의 식이 성립하면, 일단 리스트에 3을 포함시킬 수 있습니다.

위와 같은 아이디어로, make_target_from123() 함수를 아래와 같이 구현할 수 있습니다.

def make_target_from123(length123: int, target: int):     num123 = 3     answer = []     while target > 0:         if length123 - 1 <= target - num123 <= (length123 - 1) * 3:             answer.append(num123)             target -= num123             length123 -= 1         else:             num123 -= 1     answer.sort()     return answer

변수 num123은 1, 2, 3중에 가장 큰 숫자인 3부터 시작합니다.

while 루프는 target이 0이 되면 멈추도록, target > 0 동안 실행합니다.

length123에서 1을 빼고, target에서 num123을 빼도, if 문이 성립하면, num123을 리스트에 포함 시킬 수 있습니다.

하지만, if 문이 성립하지 않으면, 3은 더 이상 포함시킬 수 없기 때문에, 1감소한 2를 num123에 넣습니다.

코드의 루프가 마무리 되면, 1, 2, 3으로 구성되어 있고, 합이 target과 같은 리스트를 구할 수 있습니다.

단, 여기서 주의할 점은 작은 숫자가 앞으로 와야, 사전순으로 가장 빠른 경우가 되기 때문에, answer를 리턴하기 전에 sort() 해야 합니다.

answer = [0] * idx123     for leaf in leaves:         ans = make_target_from123(len(leaf.indexes123), target[leaf.num - 1])         for idx in range(len(leaf.indexes123)):             answer[leaf.indexes123[idx]] = ans[idx]     return answer

하나의 리프 노드에서, 합이 target값이 되는, 1, 2, 3으로 구성된, 사전순으로 가장 빠른 리스트 ans를 구했습니다. 앞에서 indexes123에 저장되는 값은 solution()함수가 리턴할 배열에 숫자를 저장할 위치라고 설명했습니다. Indexes123이 가리키는 위치에, ans[idx]를 answer리스트에 저장하면, 이 문제의 답을 구할 수 있습니다.

 

궁금한 내용은 댓글, 이메일(coding.data.pul@gmail.com)로 보내주세요.

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul

 

전체 코드는 아래와 같습니다.

from collections import defaultdict from typing import List, Optional class Node:     def __init__(self, node_num, target):         self.num = node_num         self.children: List[Optional[Node]] = []         self.target = target         self.idx_child = 0         self.indexes123: List[int] = []     def send_num123(self, idx123):         if len(self.children) == 0:             self.indexes123.append(idx123)             return not len(self.indexes123) > self.target         rtn = self.children[self.idx_child].send_num123(idx123)         self.idx_child = (self.idx_child + 1) % len(self.children)         return rtn     def __lt__(self, other):         return self.num < other.num def num123_make_target(leaves):     for idx in range(len(leaves)):         if not len(leaves[idx].indexes123) <= leaves[idx].target <= len(leaves[idx].indexes123) * 3:             return False     return True def make_target_from123(length123: int, target: int):     num123 = 3     answer = []     while target > 0:         if length123 - 1 <= target - num123 <= (length123 - 1) * 3:             answer.append(num123)             target -= num123             length123 -= 1         else:             num123 -= 1     answer.sort()     return answer def solution(edges: List[List[int]], target: List[int]):     nodes = defaultdict(lambda : None)     for parent_num, child_num in edges:         if nodes[parent_num] is None:             nodes[parent_num] = Node(parent_num, target[parent_num - 1])         if nodes[child_num] is None:             nodes[child_num] = Node(child_num, target[child_num - 1])         nodes[parent_num].children.append(nodes[child_num])     leaves: List[Node] = []     for node_num in nodes.keys():         if len(nodes[node_num].children) > 0:             nodes[node_num].children.sort()         else:             leaves.append(nodes[node_num])     idx123 = 0     while True:         if False == nodes[1].send_num123(idx123):             return [-1]         idx123 += 1         if num123_make_target(leaves):             break     answer = [0] * idx123     for leaf in leaves:         ans = make_target_from123(len(leaf.indexes123), target[leaf.num - 1])         for idx in range(len(leaf.indexes123)):             answer[leaf.indexes123[idx]] = ans[idx]     return answer

 

궁금한 내용은 댓글, 이메일(coding.data.pul@gmail.com)로 보내주세요.

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul