코테연습 트리

2023 카카오 1,2,3 떨어트리기

import math

class Node(object):
    def __init__(self, item):
        self.item = item
        self.child_current = 0
        self.child = []
        self.sum = 0
        
def downNumber(node):
    if len(node.child)==0:
        node.sum+=1
        return node.item
    else:
        next = node.child_current
        if len(node.child)-1>next:
            node.child_current += 1
        else:
            node.child_current = 0
        return downNumber(node.child[next])

def makeTree(edges):
    edges.sort(key=lambda x:(x[0],x[1]))
    
    node_item_list = list(set(sum(edges,[])))
    
    node_list = []
    
    for node_item in node_item_list:
        node_list.append(Node(node_item))
    
    for start, end  in edges:
        node_list[start-1].child.append(node_list[end-1])
    
    return node_list[0]

def findNode(node):
    if not node:
        return
    for child in node.child:
        findNode(child)

def Divide(a, b, start): # start는 분할에서 처음에 빼기 시작하는 수
    if start>3:
        return []
    r_lst = [] 
    if b != 1: # a에서 start를 뺀 후 남은 수를 마저 분할, 이후 start에 1씩 더해가며 반복
        for s in range(start, int(a / b) + 1):
            div_lst = Divide(a - s, b - 1, s)
            for lst in div_lst: # 마저 분할한 각 list를 s와 합친다
                r_lst.append([s] + lst)
    else: # b가 1이면 a만 list에 담아 return
        r_lst.append([a])
    return r_lst

def listOver3(list):
    for i in list:
        if i>3:
            return False
    return True

def solution(edges, target):
    answer = []
    order = []
    end_list = [0 for i in range(len(target))]
    root = makeTree(edges)
    mindrop = [math.ceil(i/3) for i in target]
    
    while True:
        run=0
        end_node_item = downNumber(root)-1
        end_list[end_node_item] += 1
        order.append(end_node_item)
        for idx,end in enumerate(end_list):
            if end*3 >= target[idx]:
                run+=1
        if run == len(target):
            break
    templist = []
    for idx,end in enumerate(end_list):
        if end > target[idx]:
            return [-1]
        dividelist = []
        if end>1:
            filter3list = list(filter(listOver3,Divide(target[idx],end,1)))
            dividelist = filter3list[0]
        else:
            dividelist.append(target[idx])
        templist.append(dividelist)
    for i in order:
        answer.append(templist[i].pop(0))

    
    return answer

솔직하게 코드가 너무 스타게티다..
중요점은 트리를 만들고
트리를 순차적으로 돌면서 최소 횟수의 경우 수를 찾는다.
과정에서 일부 노드가 조건을 넘어가면 -1
아니면 1~3의 숫자중에 적절한 숫자로 나누어 결과에 표현한다.
결과를 보낼때는 이전에 순차적으로돌며 떨어지는 숫자가 들가는 마지막노드의 순서를 기록해놓았다 그대로 보내주면 끝이다.

가장 오래걸린 부분은 숫자를 3~1로 나누어 주는 부분이였다. 빠르게 풀 수 있게 재귀로 돌아가는 모습을 잘 그려봐야겠다.