글 읽기 - 시간이 왜이렇게 오래걸릴까요??

shjohw12 2년 전 0

pypy로 100ms대 나오시는 분들도 많은데 저는 4초 가까이 나왔습니다. 코드에서 어느 부분이 비효율적인걸까요?

import sys

a = [[" " for y in range(3 ** 8)] for x in range(3 ** 8)]

n = int(sys.stdin.readline())


def solve(x1, x2, y1, y2):
    if x2 - x1 + 1 == 3:
        for x in range(x1, x2 + 1):
            for y in range(y1, y2 + 1):
                a[x][y] = "*"
        a[x1 + 1][y1 + 1] = " "
        return

    d = (x2 - x1 + 1) // 3

    for x in range(3):
        for y in range(3):
            if x == 1 and y == 1:
                continue
            solve(x1 + x * d, x1 + (x + 1) * d - 1, y1 + y * d, y1 + (y + 1) * d - 1)


solve(0, n - 1, 0, n - 1)

for i in range(n):
    for j in range(n):
        print(a[i][j], end="")
    print("")

djm03178 2년 전 0

우선 print가 너무 느리기 때문에 이를 sys.stdin.write로 바꾸는 것만으로도 1.5초 정도로 줄어듭니다.

그리고 문제의 제한이 3^7까지이기 때문에 a의 크기를 3^7 * 3^7로 바꾸면 0.6초 정도까지 줄어듭니다.

그 외에는 파이썬의 재귀가 느리다는 점이나 모든 원소를 str로 관리하고 있는 점 등이 조금 비효율적일 수 있을 것 같습니다.

shjohw12 2년 전 0

감사합니다!

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

문제

문제

출처

ICPC

시간이 왜이렇게 오래걸릴까요??

shjohw12 2년 전 0

djm03178 2년 전 0

shjohw12 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말