글 읽기 - [python3] 시간초과 질문드립니다

ppirae 3년 전 0

우선 에스토라테네스의 체로 500000까지 소수를 저장했습니다.

그 후에는 문제에서 말하는대로 구현만 했는데 시간초과가 발생했습니다.

아무래도 in 부분에서 나는거 같은데 저 부분을 어떻게 탐색해야 통과할지 잘 모르겠습니다.

이분탐색으로 처리해야 하나요? 시간초과 해결할 수 있는 힌트 부탁드립니다.

import sys
import math
input = sys.stdin.readline
n = 5000001
prime = [True for i in range(n)]
prime[0] = False
prime[1] = False
for i in range(2, int(math.sqrt(n))+1):
    if prime[i] == True:
        j = 2
        while i*j <= n:
            prime[i*j] = False
            j += 1

dw_score = 0
dw = []
ks_score = 0
ks = []
t = int(input())
for i in range(t):
    a, b = map(int,input().split())
    if a in ks or a in dw:
        dw_score -= 1000
    else:
        if prime[a] == True:
            dw.append(a)
        else:
            if len(ks) < 3:
                ks_score += 1000
            else:
                sorted(ks, reverse = True)
                ks_score += ks[2]
    if b in dw or b in ks:
        ks_score -= 1000
    else:
        if prime[b] == True:
            ks.append(b)
        else:
            if len(dw) < 3:
                dw_score += 1000
            else:
                sorted(dw, reverse = True)
                dw_score += dw[2]

if dw_score > ks_score:
    print("소수의 신 갓대웅")
elif dw_score < ks_score:
    print("소수 마스터 갓규성")
else:
    print("우열을 가릴 수 없음")

du9172 2년 전 0

31번 42번처럼 매번 정렬하시지 말고 우선순위 큐 자료구조 검색해서 한번 보시고 적용해보세요!

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

문제

문제

출처

ICPC

[python3] 시간초과 질문드립니다

ppirae 3년 전 0

du9172 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말