글 읽기 - 이건 파이썬으로 풀 수 없는 건가요?

friend1226 3년 전 0

시간을 줄인다고 노력해봤지만 결국 시간 초과라고 하네요

다른 언어로 풀어야 하나요?

아니면 pypy로 통과한 사람이 있는데, 이 문제를 풀 수 있는 또 다른 방법이 있나요?

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
alphabetOfWords = dict([(chr(i), set()) for i in range(ord('a'), ord('z')+1)])
# 알파벳을 가지고 있는 단어들 (예: 'a' - {'apple', 'banana', ...})
knownWords = dict()
# 단어 기억 여부 (단어 - 잊은 알파벳 개수)
for _ in range(n):
    w = input().rstrip()
    knownWords[w] = 0 # 처음에는 모두 기억하고 있음
    for l in w:
        alphabetOfWords[l].add(w) # 각 알파벳마다 단어 추가

knownN = n # 완전히 알고 있는 단어 개수
r = [] # 쿼리마다 출력할 리스트
for _ in range(m):
    c, l = input().split()
    if c=='1': # 잊기
        for w in alphabetOfWords[l]: # 알파벳을 갖고 있는 각 단어마다
            if knownWords[w]==0: # 완전히 알고 있는 상태라면
                knownN -= 1 # 이제 이 단어는 완전히 알고 있지 않은 상태
            knownWords[w] += 1 # 모르는 알파벳 (개수) 추가
    else: # 떠올리기
        for w in alphabetOfWords[l]:
            knownWords[w] -= 1 # 모르는 알파벳 (개수) 제거
            if knownWords[w]==0: # 모르는 알파벳이 없으면
                knownN += 1 # 이 단어는 완전히 아는 상태
    r.append(knownN)
print('\n'.join(map(str, r)))

sait2000 3년 전 0

적당한 전처리를 하면 쿼리 당 O(1)에 풀 수 있습니다

danbi2990 3년 전 0

혹시 이거 해결되셨나요?

파이썬으로 시간 초과 극복하기가 어렵네요.

힌트 좀 주시면 감사하겠습니다.

friend1226 3년 전 0

파이썬 포기하고 c로 풀었습니다...

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

문제

문제

출처

ICPC

이건 파이썬으로 풀 수 없는 건가요?

friend1226 3년 전 0

sait2000 3년 전 0

danbi2990 3년 전 0

friend1226 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말