소프티어

거리 합 구하기 문제에서 자료구조 방식에 따라 결과가 다르게 나와 질문 드립니다.

테스트 케이스 52-2에서 딕셔너리로 구현시 6133.0ms(1918.98mb)로 시간초과가 나오고 리스트로 구현시 5676.0ms(2125.36mb)로 정답이 나옵니다. 또한, 딕셔너리와 리스트를 섞어서 쓸 경우에는 정답 여부가 오락가락합니다. 

분명 탐색속도는 리스트보다 딕셔너리가 더 빠르다고 알고있는데 리스트로 구현하는 게 더 빠른 이유가 뭘까요?

또, 문제를 풀 때 리스트로 풀지 딕셔너리로 풀지 구분하는 방법이 있을까요?

아래는 딕셔너리로 구현한 코드입니다.

import sys
sys.setrecursionlimit(10**6)

N = int(input())

class Node:
    def __init__(self, index) -> None:
        self.index = index
        self.children = dict()
        self.distance_sum_to_leaf_node = 0
        self.subtree_size = 0

nodes = dict()
for i in range(N):
    nodes[i + 1] = Node(i + 1)
root_node = nodes[1]

def get_root_distance_with_subtree(current_node : Node, parent : Node):
    current_node.subtree_size = 1
    for child_index, child_distance in current_node.children.items():
        child_node = nodes[child_index]
        if child_node is not parent:
            get_root_distance_with_subtree(child_node, current_node)
            current_node.distance_sum_to_leaf_node += child_node.subtree_size * child_distance + child_node.distance_sum_to_leaf_node
            current_node.subtree_size += child_node.subtree_size
    return

def get_all_distance(current_node : Node, parent : Node):
    for child_index, child_distance in current_node.children.items():
        child_node = nodes[child_index]
        if child_node is not parent:
            child_node.distance_sum_to_leaf_node = current_node.distance_sum_to_leaf_node + child_distance * (N - 2 * child_node.subtree_size)
            get_all_distance(child_node, current_node)

for _ in range(N - 1):
    i, j, t = map(int, input().split()) 
    nodes[i].children[j] = t
    nodes[j].children[i] = t

get_root_distance_with_subtree(root_node, root_node)
get_all_distance(root_node, root_node)

for node in nodes.values():
    print(node.distance_sum_to_leaf_node)

아래는 리스트로 구현한 코드입니다.

import sys
sys.setrecursionlimit(10**6)

N = int(input())

class Node:
    def __init__(self, index) -> None:
        self.index = index
        self.children = list()
        self.distance_sum_to_leaf_node = 0
        self.subtree_size = 0

nodes = list()
nodes.append(Node(0))
for i in range(N):
    nodes.append(Node(i + 1))
root_node = nodes[1]

def get_root_distance_with_subtree(current_node : Node, parent : Node):
    current_node.subtree_size = 1
    for child_index, child_distance in current_node.children:
        child_node = nodes[child_index]
        if child_node is not parent:
            get_root_distance_with_subtree(child_node, current_node)
            current_node.distance_sum_to_leaf_node += child_node.subtree_size * child_distance + child_node.distance_sum_to_leaf_node
            current_node.subtree_size += child_node.subtree_size
    return

def get_all_distance(current_node : Node, parent : Node):
    for child_index, child_distance in current_node.children:
        child_node = nodes[child_index]
        if child_node is not parent:
            child_node.distance_sum_to_leaf_node = current_node.distance_sum_to_leaf_node + child_distance * (N - 2 * child_node.subtree_size)
            get_all_distance(child_node, current_node)

for _ in range(N - 1):
    i, j, t = map(int, input().split()) 
    nodes[i].children.append((j, t))
    nodes[j].children.append((i, t))

get_root_distance_with_subtree(root_node, root_node)
get_all_distance(root_node, root_node)

for node in nodes[1:]:
    print(node.distance_sum_to_leaf_node)

감사합니다. :)