글 읽기 - Python, pypy 어떻게 통과 하셨져..?

fud0427 3년 전 0

코드에서 줄일 수 있는 시간은 다 줄였다고 생각합니다만...

이중 for문 한번 도니까 n**2이고

키 값으로 한번 도니까 n**2아닌가요...

구글링 해서 블로그에 있는 다른 분 코드 넣어봤는데 성공한 코드도 있고 실패한 코드도 있네요

근데 두 코드 모두 이중 for문을 두 번 사용했습니다...ㅜㅜ

도대체 왜!!!시간 초과인지 통과하셨거나 파잘알 분들 답변 부탁드립니다ㅜㅜㅜㅜㅜㅜ

import sys
from collections import defaultdict

n=int(sys.stdin.readline())
A,B,C,D=[],[],[],[]
for i in range(n):
    a,b,c,d=map(int, sys.stdin.readline().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

ab=defaultdict(int)
cd=defaultdict(int)
for i in range(n):
    for j in range(n):
        ab[A[i]+B[j]]+=1
        cd[C[i]+D[j]]+=1

res=0
for i in ab.keys():
    if cd[-i]:
        res+=(ab[i]*cd[-i])
print(res)

djm03178 3년 전 2

dict는 시간 복잡도만 평균 O(1)일 뿐, 숨어있는 상수가 매우 큽니다. 사실상 로그가 붙은 코드들과 비슷하거나 더 오래 걸린다고 생각하시면 됩니다.

fud0427 3년 전 0

@djm03178

헉 그렇군요 감사합니다ㅜㅜ 메모리 제한범위가 넉넉하니 2차원 리스트로 풀어보겠습니다

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

문제

문제

출처

ICPC

Python, pypy 어떻게 통과 하셨져..?

fud0427 3년 전 0

djm03178 3년 전 2

fud0427 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말