글 읽기 - [pypy3] 시간초과...

eehwan 3년 전 0

어느부분에서 시간을 많이 잡아먹는건가요?

어떻게 고치면 시간초과를 피할 수 있을까요??

import sys

rep = int(sys.stdin.readline())
for _ in range(rep):
    ppl = int(sys.stdin.readline())
    scores = sorted([list(map(int, sys.stdin.readline().split())) for _ in range(ppl)],key= lambda x:x[0])
    for score_1 in scores:
        for score_2 in scores[scores.index(score_1)+1:]:
            if score_1[1] < score_2[1]:
                scores.remove(score_2)
    print(len(scores))

shg9411 3년 전 1

index와 remove 모두 수행시간이 긴 작업들입니다.

eehwan 3년 전 0

그렇군요ㅜㅜ 답변 감사합니다

완전히 다른방법을 강구해봐야겠네요

eehwan 3년 전 0

이렇게 고쳐봤는데 여전히 시간초과가 뜨더라구요ㅠㅠ

더 나은 방법이 있을까요?

import sys

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

for _ in range(rep):
    ppl = int(sys.stdin.readline())
    scores = sorted([list(map(int, sys.stdin.readline().split())) for _ in range(ppl)],key= lambda x:x[0],reverse=True)
    count = ppl
    for i in range(ppl):
        for j in range(i+1,ppl):
            if scores[i][1] > scores[j][1]:
                count-=1
                break
    print(count)

shg9411 3년 전 1

입력이 최대 10만이기에 n^2으로는 시간초과가 날 수 밖에 없습니다.

정렬 을 하시면 이후 for문 한번으로 답을 도출하실 수 있습니다.

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

문제

문제

출처

ICPC

[pypy3] 시간초과...

eehwan 3년 전 0

shg9411 3년 전 1

eehwan 3년 전 0

eehwan 3년 전 0

shg9411 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말