글 읽기 - 파이썬 시간초과입니다!

a1clsrotorl 7달 전 0

입력을 map이랑 readline을 사용해봤는데도 시간초과가 나네요. 어떻게 해야 시간을 더 줄일 수 있을까요? 이게 문제가 아니라면 코드에서 시간이 낭비되는 구간이 어디일까요?

# 그리디 : 1202 다시할 것

# V를 기준으로 리스트에 집어넣고 정렬 후, 무게가 맞는지 확인
# 무게가 적당하다면 value에 더한 다음 삭제, 아니라면 다음 인덱스 확인
import heapq
from sys import stdin, stdout

n, k = map(int, stdin.readline().split())
q = [] # 보석 정보를 저장할 heapq
value = 0
c = list() # 가방 정보를 저장할 list

for index in range(n): # 보석별 무게와 가치를 q에 저장
    m, v = map(int, stdin.readline().split())
    heapq.heappush(q, [v*(-1), m])
    
for index in range(k): # 가방 capacity를 저장
    c.append(int(stdin.readline()))
    
for index in range(k):
    for index2 in range(len(q)):
        if c[index] >= q[index2][1]:
            value += q[index2][0] * (-1)
#             heapq.heappop(q[index2])
            del q[index2]
            break
        else:
            continue
    
print(value)

ssr3588 7달 전 1

n이랑 k가 최대 30만개라 20번째 줄부터 이중 for문을 사용하게 되면 시간초과가 될거에요..

그리고 25번째 줄도 O(n)복잡도라 시간초과가 났을것 같네요.

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

문제

문제

출처

ICPC

파이썬 시간초과입니다!

a1clsrotorl 7달 전 0

ssr3588 7달 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말