글 읽기 - [python] list의 append 시간 차이

dksrudmoe 2년 전 0

dot1 함수는 리스트를 []로 선언하고 append로 원소를 추가해주었구요

dot2 함수는 [None] * n, [0] * n 등을 사용해서 배열을 사이즈에 맞게 미리 선언했는데요.

근데 dot2 쓸때만 시간초과가 발생합니다.

원래 c++에서는 vector를 사용할 때 계속 push_back 하는 것보다 미리 크기에 맞춰서 선언하는 것이 속도가 더 빠르다고 알고 있는데

파이썬 list는 오히려 미리 선언해주었을 때 시간초과가 나는데요 이유가 있나요?

def dot1(a, b):
   x, y, z = len(a), len(b[0]), len(b)
   result = []
   for i in range(x):
      temp = []
      for j in range(y):
         m = 0
         for k in range(z):
            m += a[i][k]*b[k][j]
         temp.append(m % 1000)
      result.append(temp)
   return result

def dot2(a, b):
   x, y, z = len(a), len(b[0]), len(b)
   result = [None] * x
   for i in range(x):
      result[i] = [0] * y
      for j in range(y):
         for k in range(z):
            result[i][j] += a[i][k]*b[k][j]
         result = result % 1000
   return result

n, b = map(int, input().split())
arr = [None] * n
for i in range(n):
   arr[i] = list(map(int, input().split()))
answer = [None] * n
for i in range(n):
   answer[i] = [0] * n
   answer[i][i] = 1

while b > 0:
   if b % 2 == 1:
      answer = dot1(answer, arr)
   arr = dot1(arr, arr)
   b //= 2
for i in range(n):
   for j in range(n):
      print(int(answer[i][j]), end=' ')
   print()

woosukji 2년 전 1

올려주신 코드의 dot2() 에서,

result = result % 1000 로 list를 int로 나누고 있어, 시간 초과가 아닌 오류가 발생할 것이구요.

질문자님의 제출 기록을 확인해 보니,

19번 줄에서 temp[j] % 1000 라고 선언만 할 뿐 값을 저장하지 않고 있네요.

나머지 연산이 안된 상태로 큰 수를 연산하다 보니 (최대 5000 ^ (10^11) 정도), 틀렸습니다가 아닌 시간 초과가 나는 것입니다.

첫 케이스부터 상당히 큰 엣지 케이스를 주는 것 같아요.

dksrudmoe 2년 전 0

아 제가 [i][j]를 빼먹었네요

도움 주셔서 감사합니다

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

문제

문제

출처

ICPC

[python] list의 append 시간 차이

dksrudmoe 2년 전 0

woosukji 2년 전 1

dksrudmoe 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말