글 읽기 - 시간초과 문의드립니다.

leekm12 3년 전 0

이중for문 문제인가 하고 for문을 최대한 줄였는데도 시간초과가 뜨네요 .. 어디서 문제가 발생한건지 혹시 알수 있을까요 ?

시간초과가 계속 뜹니다 .. 읽어주셔서 감사합니다 !

import sys
n=int(sys.stdin.readline())
arr=[]
for i in range(n):
    arr.append(int(sys.stdin.readline()))
push_count=0
pop_count=0
count=[]
i=0
while i<n:
    if i==0:
        push_count+=arr[0]
        count.append(["+",push_count])
        count.append(["-",1])
        pop_count+=1
    elif arr[i-1]<arr[i]:
        a=arr[:i]
        m=max(a)
        push_count+=arr[i]-m
        count.append(["+",arr[i]-m])
        count.append(["-",1])
        pop_count+=1
    elif arr[i-1]>arr[i]:
        pop_count+=1
        count.append(["-",1])
    i+=1
if push_count==n and pop_count==n:
    for i in count:
        print(f"{i[0]}\n"*i[1],end="")
else:
    print("NO")

slah007 3년 전 1

for라는 글자가 없어진다고 시간복잡도가 줄어들지 않습니다.

18번 줄에서 max(arr[:i]) 는 i개의 값을 전부 탐색하여 O(i)의 시간이 필요하므로 i=1~N에 대해 수행하면 O(N^2)입니다. 아마 의도하신건 O(N)일겁니다.

잘 생각해보면 max를 구할 때마다 i개 값을 다 볼 필요가 없습니다.

leekm12 3년 전 0

감사합니다 ! max 를 고치니까 해결이 되네요 ㅎㅎㅎ

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

문제

문제

출처

ICPC

시간초과 문의드립니다.

leekm12 3년 전 0

slah007 3년 전 1

leekm12 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말