글 읽기 - [python] set을 이용하여 풀었는데, 시간복잡도상 궁금한게 있습니다.

cyhh333 2년 전 0

combination을 이용해서

가르칠 수 있는 알파벳의 모든 조합을 구한 뒤

각 조합마다 몇개의 단어를 가르칠 수 있는지 진행했습니다.

처음에는 예상대로 시간초과가 났습니다.

코드도 좀 지저분한 것 같고, 중간에 in 연산이 찝찝했기에 시간초과가 날 것 같았습니다.

어떻게 고쳐볼까 하다가 set 자료형을 이용해서 부분집합 비교연산을 이용해보면 어떨까 해서

해당 과정으로 진행해보았더니 시간초과가 나지 않았습니다.

set 자료형을 이용했을 뿐, 완전탐색의 큰 흐름은 차이가 없어보이는데

set 자료형을 사용했을 때 시간초과가 나지 않는 이유가 궁금합니다.

부분집합 비교연산은 시간복잡도가 작은 연산인지 궁금합니다.

from sys import stdin
from itertools import combinations

wordNum, letterNum = map(int, stdin.readline().rstrip().split(' '))

if letterNum < 5 :
    print(0)
    exit(0)

base = ['a', 'n', 't', 'i', 'c']
other = "bdefghjklmopqrsuvwxyz"
other = list(other)
candidates = list(combinations(other, letterNum - 5))

words = []
for _ in range(wordNum) :
    words.append(stdin.readline())

result = 0
for candidate in candidates :
    possible = tuple(base) + candidate
    tmp = 0
    for word in words :
        wordLen = len(word)
        cnt = 0
        for i in range(4, wordLen - 4) :
            if word[i] in possible :
                cnt += 1
        if cnt == wordLen - 8 :
            tmp += 1
    if tmp > result :
        result = tmp

print(result)


########################### 위 : 초기 코드, 아래 : set 코드  ##################

from sys import stdin
from itertools import combinations

wordNum, letterNum = map(int, stdin.readline().rstrip().split(' '))

if letterNum < 5 :
    print(0)
    exit(0)

base = {'a', 'n', 't', 'i', 'c'}
other = "bdefghjklmopqrsuvwxyz"
other = list(other)

wordSets = []
allSet = set({})
for _ in range(wordNum) :
    wordSet = set(stdin.readline().rstrip())
    wordSets.append(wordSet)
    allSet |= wordSet

otherSet = allSet - base

otherSetLen = len(otherSet)
if otherSetLen <= letterNum - 5 :
    print(wordNum)
    exit(0)
else :
    candidates = combinations(otherSet, len(otherSet) - (letterNum - 5))

result = 0
for candidate in candidates :
    tmpSet = allSet - set(candidate)
    cnt = 0
    for wordSet in wordSets :
        if wordSet <= tmpSet :
            cnt += 1
    if result < cnt :
        result = cnt

print(result)

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

문제

문제

출처

ICPC

[python] set을 이용하여 풀었는데, 시간복잡도상 궁금한게 있습니다.

cyhh333 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말