글 읽기 - 시간 더 줄일 수 있는 방법 있을까요?

fox9101 3년 전 0

파이썬3 시간초과 나옵니다. 시간 더 줄일 수 있는 방법 있을까요?

import sys
read = lambda : sys.stdin.readline().rstrip()
def count():
    cnt = 0
    for word in words:
        ok = True
        for x in word:
            if (check[ord(x)-97] != True):
                ok = False
                break
        if ok == True:
            cnt += 1
    return cnt
def go(index, cnt):
    global answer
    if cnt == k:
        answer = max(answer, count())
        return
    for i in range(index, 26):
        if check[i] == True:
            continue
        check[i] = True
        go(i+1, cnt+1)
        check[i] = False
 
n, k =map(int,read().split())
k -= 5
words = [read()[4:-4] for _ in range(n)]
check = [False] * 26
check[ord('a')-97] = True
check[ord('n')-97] = True
check[ord('t')-97] = True
check[ord('i')-97] = True
check[ord('c')-97] = True
index = 0
cnt = 0
answer = 0
if k < 0:
    print(answer)
elif k == 26:
    print(n)
else:
    go(index, cnt)
    print(answer)

wider93 3년 전 0

check를 dict 또는 bitmask로 구현해서 a,n,t,i,c를 따로 처리하면 20번 줄을 뺄 수 있어서 좀 더 빨라질 것이고요,

word마다 전처리를 해서 count 함수의 실행시간도 줄일 수 있을 것 같습니다.

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

문제

문제

출처

ICPC

시간 더 줄일 수 있는 방법 있을까요?

fox9101 3년 전 0

wider93 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말