글 읽기 - 왜 시간초과가 나올까요...... 이럴 순 없습니다...

chminoo 2년 전 0

사지방에서 백준풀고있는 제인생이 레전드인건압니다...

하지만...

국방부 시계도 안흘러가는데... 시간초과??? 라는 단어는 굉장히 화가납니다....

오랜만에 파이썬 잡아서 그런가 감이 잘 안잡혀서 그런거일 수도 있는데 시간초과는 상당히 이해가 안됩니다.

아마 느낌상 최대힙에 집어넣고 빼고 넣고 빼고 하는 과정에서 시간오래걸릴거 같긴한데 heappop과 heappush는 기억상 O(logN) (빠르다)의 시간복잡도를 갖는 함수인데 이게 오래걸리나 싶기도하고...

라고 글적다 보니 뭔가 in과 not in으로 서치하는 부분이 느린거같기도 합니다.

왜 저는 항상 질문글 적다가 애매한곳에서 정답을 찾는걸까요....

import sys
import heapq


def prime(n):
    sieve = [True] * n
    
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i]:          
            for j in range(i+i, n, i): 
                sieve[j] = False

    return [i for i in range(2, n) if sieve[i]]
    

prime_list = prime(5000000)
N = int(sys.stdin.readline())
stack_dae = []
stack_kyu = []
chk = []
score_dae = 0
score_kyu = 0

for _ in range(N):
    dae, kyu = map(int, sys.stdin.readline().split())
    if dae in prime_list:
        if dae not in chk:
            heapq.heappush(stack_dae, (-dae, dae))
            chk.append(dae)
        else:
            score_dae -= 1000
    else:
        if len(stack_dae) < 3:
                score_kyu += 1000
        else:
            temp = []
            for i in range(3):
                temp.append(heapq.heappop(stack_dae))
            score_kyu += temp[2][1]
            for i in range(3):
                heapq.heappush(stack_dae, temp[i])

    if kyu in prime_list:
        if kyu not in chk:
            heapq.heappush(stack_kyu, (-kyu, kyu))
            chk.append(kyu)
        else:
            score_kyu -= 1000
    else:
        if len(stack_kyu) < 3:
                score_dae += 1000
        else:
            temp = []
            for i in range(3):
                temp.append(heapq.heappop(stack_kyu))
            score_dae += temp[2][1]
            for i in range(3):
                heapq.heappush(stack_kyu, temp[i])

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

chminoo 2년 전 0

이젠 시간초과를 해결했더니 틀렸습니다가 뜹니다...

역시 제 군생활은 틀린걸로...

import sys
import heapq
from collections import defaultdict


def prime(n):
    sieve = [True] * n
    
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:          
            for j in range(i+i, n, i): 
                sieve[j] = False

    return [i for i in range(2, n) if sieve[i] == True]
    

prime_list = defaultdict(lambda:False)

for i in prime(5000000):
    prime_list[i] = True

stack_dae = []
stack_kyu = []

chk = defaultdict(lambda:True)
score_dae = 0
score_kyu = 0

for _ in range(int(sys.stdin.readline())):
    dae, kyu = map(int, sys.stdin.readline().split())
    if prime_list[dae]:
        if chk[dae]:
            heapq.heappush(stack_dae, (-dae, dae))
            chk[dae] = False
        else:
            score_dae -= 1000
    else:
        if len(stack_dae) < 3:
                score_kyu += 1000
        else:
            temp = []
            for i in range(3):
                temp.append(heapq.heappop(stack_dae))
            score_kyu += temp[2][1]
            for i in range(3):
                heapq.heappush(stack_dae, temp[i])

    if prime_list[kyu]:
        if chk[kyu]:
            heapq.heappush(stack_kyu, (-kyu, kyu))
            chk[kyu] = False
        else:
            score_kyu -= 1000
    else:
        if len(stack_kyu) < 3:
                score_dae += 1000
        else:
            temp = []
            for i in range(3):
                temp.append(heapq.heappop(stack_kyu))
            score_dae += temp[2][1]
            for i in range(3):
                heapq.heappush(stack_kyu, temp[i])

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

chminoo 2년 전 0

핫하 집념의 대한해군

결국 해내고 말았습니다.

이문제가 국어문제라는것을 알기전까지는...

소수가 아닌 수를 부르게 될 경우 상대방은 지금까지 상대방이 말한 소수중에서 3번째로 큰 수만큼 점수를 얻게 된다.(만약 상대방이 지금까지 말한 소수가 3개 미만이라면 상대방은 1000점을 얻게 된다.)

상대방은 지금까지 상대방이

라는 표현이

당연히 상대방의 상대방인줄 알았는데

ㄹㅇ 문자 그대로의 상대방이라는 것에 대해서 당황했습니다.

이렇게 표현할꺼면... 상대방은 지금까지 자신이 말한 소수중에서

라는 표현이 맞지 않나 싶습니다.... 아이고 대가리야

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

문제

문제

출처

ICPC

왜 시간초과가 나올까요...... 이럴 순 없습니다...

chminoo 2년 전 0

chminoo 2년 전 0

chminoo 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말