글 읽기 - [파이썬] 11725 시간 초과

qwer15417 2년 전 1

python3로 제출하면 시작부터 시간 초과가 뜨고

pypy로 제출하면 잘 나가다가 시간 초과가 뜨는데요.

트리를 만들어 나가면서 부모 노드를 리스트에 추가했습니다.

이 코드가 제가 생각하는 최선인데 어느 부분에서 비효율이 발생하였는지 궁금합니다.

도움을 주십쇼 고수님들!

import sys
import collections


# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.child = []


N = int(sys.stdin.readline())
graph = collections.defaultdict(list)
for _ in range(N - 1):
    a, b = list(map(int, sys.stdin.readline().split()))
    graph[a].append(b)
    graph[b].append(a)

parent_list = [0] * (N + 1)

used = [1]
root = TreeNode(1)
queue = collections.deque([root])

while queue:
    node = queue.popleft()
    i = -1
    while graph[node.val]:
        val = graph[node.val].pop()
        if val in used:
            continue
        used.append(val)
        i += 1
        node.child.append(TreeNode(val))
        parent_list[val] = node.val
        queue.append(node.child[i])

for i in range(2, N + 1):
    print(parent_list[i])

yijw0930 2년 전 4

line30에서 val in used는 O(n)이 필요하므로 비효율적입니다.

길이 n+1의 false로 채워진 list를 만들어 used.append(val) 대신 used[val]=true 와 같을 식으로 체크하면 시간을 많이 줄일 수 있습니다.

qwer15417 2년 전 0

생각지도 못했네요. 좋은 답변 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[파이썬] 11725 시간 초과

qwer15417 2년 전 1

yijw0930 2년 전 4

qwer15417 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말