글 읽기 - [Python] 시간 초과 어떻게 해결하면 좋을까요

jun0w7 1년 전 0

Counter 함수와 빠른 입력을 사용했는데도 시간초과가 발생하는데 혹시 여기서 시간을 더 줄일 수 있는 방법이 있을까요?

아니면 혹시 조건 분기문이 잘못돼서 시간 초과가 발생하는 것인가요?

from collections import Counter

input = __import__('sys').stdin.readline

n, k = map(int, input().split())
li = list(map(int, input().split()))
l = 0
r = 1
mx = 1

while True:
    tmp = li[l:r]
    cnt = Counter(tmp)
    cnt = cnt[tmp[-1]]
    if r == n and len(tmp) > max: 
        max = len(tmp)
        break
    elif r == n:
        break
        
    if cnt <= k and r < n:
        r += 1
        if len(tmp) > mx:
            mx = len(tmp)
    elif cnt <= k:
        l += 1
        if len(tmp) > mx:
            mx = len(tmp)
    else:
        if l < r:
            l += 1
        else:
            r += 1

print(mx)

77dptjd 10일 전 0

counter를 사용하게 되면 쓸때마다 O(N)의 시간 복잡도로 몇 개 있는지 알 수 있습니다.

저는 그래서 크기가 100,001 리스트를 만들어서 몇 개 있는지 확인할때 각 숫자의 idex 번호를 호출하는 형식으로 O(1)의 시간 복잡도로 몇 개 있는지 알 수 있게 했습니다.

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

문제

문제

출처

ICPC

[Python] 시간 초과 어떻게 해결하면 좋을까요

jun0w7 1년 전 0

77dptjd 10일 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말