글 읽기 - 시간복잡도 질문

goh1211 1년 전 0

예제는 통과했습니다.

N * N + M (2000 * 2000 + 1000000)정도의 시간복잡도가 나온다고 생각하고 제출했는데,

1~2%에서 시간초과가 뜹니다.

아무리 파이썬이라지만, 저 정도는 1.5초 안에 해결할 것 같은데,

제가 시간복잡도를 잘못 계산한 건가요?

잘못 계산했다면, 시간복잡도 좀 알려주실 수 있을까요?

from collections import deque

N = int(input())

numbers = list(map(int, input().split()))

num_info = deque([deque() for _ in range(len(numbers))])

for i in range(2, len(numbers)):
    if i -2 >= 0:
        if numbers[i] == numbers[i-2]:
            num_info[i].append(i-2)
        
    if i - 3 >= 0:
        if numbers[i] == numbers[i-3] and numbers[i-1] == numbers[i-2]:
            num_info[i].append(i-3)
        
    for j in num_info[i-1]:
        if j -1 >= 0:
            if numbers[j] == numbers[i]:
                num_info[i].append(j-1)
                

M = int(input())

for _ in range(M):
    s, e = map(int, input().split())
    s -= 1
    e -= 1
    if s in num_info[e] or s == e:
        print(1)
    else:
        print(0)
    

goh1211 1년 전 0

아 26줄 에서 in을 쓰네요. N*M + N*N이 맞는 것 같습니다.

시간초과가 뜰 만하네요.

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

문제

문제

출처

ICPC

시간복잡도 질문

goh1211 1년 전 0

goh1211 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말