글 읽기 - [파이썬] 이 코드 시간복잡도가 어떻게 되는건가요?

pyoun6599 3년 전 0

혼자서 풀어 보려는데 시간초과가 계속 나서 질문드립니다.

이 코드 시간복잡도 어느정도 되는지 논리적으로 부탁드립니다

import sys
input = sys.stdin.readline

aeiou = {'a','e','i','o','u'}
char = set([chr(97+i) for i in range(26)]) - aeiou
words = []
answer = []
N, M = map(int, input().split())
for _ in range(N):
    words.append(set(input().rstrip())-aeiou)

for _ in range(M):
    o, x = input().split()
    if o == '1':
        char.remove(x)
    else:
        char.add(x)
    
    cnt = 0
    for word in words:
        if not word - char: cnt += 1
    answer.append(cnt)
    
print('\n'.join(map(str, answer)))

WeissBlume 3년 전 0

O(nm) 처럼 보이는데 상수가 굉장히 클 것 같네요

pyoun6599 3년 전 0

먼저 답변 감사합니다.

N이 최대 10**4 이고 M이 최대 5 * 10**4 인데, 전체 5 * 10**8를 4초안에 해결하지 못하는 건가요?

WeissBlume 3년 전 1

nm번의 연산 자체가 많다기보단 무거운 연산을 nm번 하는게 문제입니다(26개짜리 string set 연산 등)

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

문제

문제

출처

ICPC

[파이썬] 이 코드 시간복잡도가 어떻게 되는건가요?

pyoun6599 3년 전 0

WeissBlume 3년 전 0

pyoun6599 3년 전 0

WeissBlume 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말