글 읽기 - python3 시간초과 문제,..

neomind75 4년 전 0

입/출력 관련해서 모두 백준에서 속도가 높다고 하는 함수들만 사용하고있고,

파이썬에서 .을 사용해 참조하게 될 때 속도지연이 발생한다고 해서 또 .을 최대한 안쓰도록 자주 호출되는 멤버함수들의 경우 별도로 변수로 만들어 참조토록 하고있습니다. 또, 리스트 데신 덱을 사용해서 속도를 높였습니다.

도대체 뭘 더해야할지 잘 모르겠네요. 제가 짠 알고리즘 자체의 문제인가 싶기도 하고..

시간초과 해결할 방법 아시는분!

import collections
import sys

n = int(input())

class Node:
    def __init__(self, parent, data):
        self.parent = parent;
        self.data = data;
        self.children = collections.deque([])

class Tree:
    def __init__(self):
        self.tree = Node(None, 1);

    def push(self, a, b):
        stack = collections.deque([self.tree])
        pop = stack.pop
        push = stack.append
        
        while (stack):
            node = pop()
            if (node.data == a):
                node.children.append(Node(node, b))
                break
            elif (node.data == b):
                node.children.append(Node(node, a))
                break;
            stack += [child for child in node.children]
                
    def result(self):
        num = 2;
        outs = collections.deque([])
        opush = outs.append
        while (num <= n):
            stack = collections.deque([self.tree])
            pop = stack.pop
            push = stack.append
            
            while (stack):                    
                node = pop()
                stack += [child for child in node.children]
                if (node.data == num):
                    opush(node.parent.data)
                    break
            num += 1
        print("\n".join(map(str, outs)))

tree = Tree()
push = tree.push

for _ in range(1, n):
    a, b = map(int,sys.stdin.readline().split())
    push(a, b)
tree.result()

cheshirecoder 4년 전 0

n개에서 시간 복잡도가 얼마라고 생각하시나요?

그리고 말씀하신 부분은 얼마나 시간이 지연된다고 생각하시나요? 실제로 벤치마크를 해봤나요?

해결할 건 시간초과가 아닌 것으로 보입니다.

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

문제

문제

출처

ICPC

python3 시간초과 문제,..

neomind75 4년 전 0

cheshirecoder 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말