글 읽기 - Python3 은 런타임 에러, pypy3 는 시간 초과?

wwaa456 4년 전 0

어떤 부분을 개선해야 할까요?

import sys
sys.setrecursionlimit(100000)
read = sys.stdin.readline

students = []
check = []
cnt = 0

def dfs(n, trace):
    global cnt
    trace.append(n)
    check[n] = len(trace)
    next = students[n]

    if check[next] == 0:
        dfs(next, trace)
    elif n == next:
        cnt -= 1
    else:
        try:
            start = trace.index(next)
            cnt -= len(trace) - start
        except ValueError:
            return

t = int(read())
for i in range(t):
    cnt = int(read())
    students = [0] + list(map(int, read().split()))
    check = [0] * len(students)

    for j in range(1, len(students)):
        if check[students[j]] == 0:
            dfs(students[j], [])

    print(cnt)

sait2000 4년 전 1

일단, 재귀 회수 제한이 작습니다. 100000보다 좀 커야 될 것 같습니다. 시간초과는... 글쎄요 잘 모르겠네요.

wwaa456 4년 전 0

왜 좀 더 커야 할까요?

sait2000 4년 전 1

2 3 4 5 6 .. 100000 1을 넣어보시면 dfs(2) dfs(3) ... dfs(100000) dfs(1)까지 호출하고 그 안에서 trace.index등도 호출하니까 100001번 이상이 됩니다.

indioindio 4년 전 0

파이선 코딩스타일에서는 ask for forgiveness(try & except) 하라지만 if 문으로 check하는 것이 더 빠를거 같습니다. 돌려보지 않아서 확답은 못드리겠네요.

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

문제

문제

출처

ICPC

Python3 은 런타임 에러, pypy3 는 시간 초과?

wwaa456 4년 전 0

sait2000 4년 전 1

wwaa456 4년 전 0

sait2000 4년 전 1

indioindio 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말