글 읽기 - 시간초과를 어떻게 개선해야할지 모르겠습니다!

sy980402 2년 전 0

하나의 테스트케이스에 대해서, 한 줄 씩 입력받으며 마지막 입력이 0 0이 아니면 노드 정보에 추가하고, 0 0을 입력받으면 모든 입력을 다 받은 것으로 판단해서 트리인지 아닌지 판별하는 로직을 수행합니다. 로직이 맞는지 틀렸는지를 떠나서, 입력받을 때도 판별 로직을 수행할 때도 전부 while, for 문이 중첩되서 그런지 시간초과가 뜹니다! 제가 봐도 코드가 어딘가 비효율적인것 같기는 한데, 어떤식으로 개선해야할지 감이 안잡혀서 질문드립니다

도움주시면 감사하겠습니다!

from sys import stdin



def testcase():
    # 하나의 테스트 케이스 에 대한 로직

    # 문제에 노드의 최대 번호 수에 대한 정보가 없네
    tree = [[] for i in range(10001)]
    nodes = set()  # 존재하는 모든 노드 번호

    while True:
        tmp = list(map(int, stdin.readline().split()))
        for i in range(0, len(tmp), 2):
            u, v = tmp[i], tmp[i + 1]
            if u != 0 or v != 0:
                # print(u, v)
                tree[v].append(u)  # tree[i] : i의 부모 노드
                # print(tree[v])

                nodes.add(u)
                nodes.add(v)

            else:
                # 한 테스트 케이스 에 대한 입력이 끝남
                # print(tree[:maxi + 1])

                # 부모 노드가 없는 노드가 단 하나 존재 해야 한다.
                # 그 외의 모든 노드는 부모가 하나 씩 존재 해야 한다.
                cnt = 0
                for node in nodes:
                    # print(node, tree[node])
                    if len(tree[node]) > 1:
                        return False
                    elif len(tree[node]) == 0:
                        cnt += 1
                        if cnt > 1:
                            return False
                return True


k = 1
while True:
    tf = testcase()
    if tf:
        print("Case " + str(k) + " is a tree.")
    else:
        print("Case " + str(k) + " is not a tree.")


    eof = stdin.readline().rstrip()
    if eof == "-1 -1":
        break


    k += 1

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

문제

문제

출처

ICPC

시간초과를 어떻게 개선해야할지 모르겠습니다!

sy980402 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말