글 읽기 - 시간초과] 알고리즘 시간 복잡도에서 어떤 부분이 문제인지 모르겠습니다.

oraclemiso 3년 전 1

대체... 뭐가 문제인지 모르겠습니다.

이거랑 비슷한 코드가 C++로 구글링 했을 때 나오기는 하는데

해당 코드는 성공하고 제꺼는 시간초과가 뜨는지 모르겠습니다.

num = int(input())

sum_weight = 0
#input list : arr | certain color's weight list : color | list ans : answer 
arr = [] 
color = []
ans = []

for i in range(num):
  arr.append([int(x) for x in (input().split(" "))])
  #append index info. at list arr
  arr[i].append(i)
  ans.append(0)
  color.append(0)
#Because Color start 1, not 0, so append one additionally.
color.append(0)

arr = sorted(arr,key=lambda l:l[1])
#print(arr)
j = 0
for i in range(num):
  while arr[i][1] > arr[j][1]:
    sum_weight += arr[j][1]
    color[arr[j][0]] += arr[j][1]
    j += 1
  ans[arr[i][2]] = (sum_weight - color[arr[i][0]])
   
for x in ans:
  print(x) 

kiki7000 3년 전 1

PyPy3으로 해보세요

코드 알고리즘이 완전 똑같은데 시간초과이면 Python 문제인겁니다

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

문제

문제

출처

ICPC

시간초과] 알고리즘 시간 복잡도에서 어떤 부분이 문제인지 모르겠습니다.

oraclemiso 3년 전 1

kiki7000 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말