글 읽기 - (파이썬)어디서 시간초과가 뜨는걸까요?.. ㅠㅠ

jewoo010 2년 전 0

deque 써서 최대한 줄여볼려했는데 시간초과가 뜨네요

제 생각엔 16줄 인덱싱하고 sum 하는 부분이 문젠거같긴합니다

고수님들 생각은 어떠신지요

# 21921 블로그
# https://www.acmicpc.net/problem/21921
import sys;
from collections import deque;
N,X = map(int, input().split());

people = list(map(int, sys.stdin.readline().split()));

visitor_sum = deque();

start = 0;
end = X-1;
summary = 0;
for start in range(len(people)):
    if end >= len(people): break;
    summary = sum(people[start:end+1]);
    # print(people[start:end+1], summary);
    visitor_sum.appendleft(summary);
    end += 1;

sorted(visitor_sum, reverse=True);
max_visior_sum = visitor_sum[0];

count =0;
for i in visitor_sum:
    if max_visior_sum == i:
        count+=1;
    else:break;
        
if max_visior_sum == 0:
    print('SAD');
else:
    print(max_visior_sum);
    print(count);

h1234000 1년 전 0

여기서 이중반복문을 쓰면 안됩니다.(슬라이싱 합도 결국 이중반복문이랑 같음)

그러면 기간동안의 방문자들을 구하는 시간복잡도 O(x) * 기간의 개수 O(n-x+1) => O(x*n) 이 됩니다.

힌트로는 기간동안의 방문자들을 구하는 시간복잡도를 낮출 방법을 생각해보셔요. O(1)만에 구하는 방법이 있습니다.

h1234000 1년 전 0

아 문제 해결하신걸 못 봤네요..ㅋㅋㅋ

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

문제

문제

출처

ICPC

(파이썬)어디서 시간초과가 뜨는걸까요?.. ㅠㅠ

jewoo010 2년 전 0

h1234000 1년 전 0

h1234000 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말