[BOJ/백준] 1062 가르침

from itertools import combinations

N,K = map(int,input().split())
ord_dict = {}
if K <5:
    print(0)
    exit()
elif K == 26:
    print(N)
    exit()
else:
    # 2**승으로 만들어 주기 위한 곳
    for k in range(26):
        ord_dict[chr(k+97)] = k

    K = K - 5
    comb_bits = 0
    # 무조건 있는 애들을 기본적으로 comb_bits로 만들어준다.
    for k in ['a','n','t','i','c']:
        comb_bits = comb_bits + 2**ord_dict[k]
    word_list = []


    for _ in range(N):
        # 앞뒤 고정 부분은 필요없으니 자른다.
        temp = set(list(input())[4:-4])
        word_list.append(temp)
    # 고정적으로 잇는 부분 제외하고 나머지를 뽑는다.
    combi_word = set(ord_dict.keys()) - set(['a','n','t','i','c'])
    result = 0
    for pick_words in combinations(combi_word,K):
        check_bits = comb_bits
        for pick_word in pick_words:
            # OR 연산을 해줘서 BIT 형식으로 만들어준다.
            check_bits = check_bits | 1<< ord_dict[pick_word]

        word_cnt = 0
        for word in word_list:
            for wo in word:
                # 만약에 AND 연산을 했는데 False가 나오면 그만둔다.
                if not (check_bits & 1<<ord_dict[wo]):
                    break
            else:
                word_cnt += 1
        result = max(word_cnt,result)
                
    print(result)

 

 

어렵지 않은 문제인데 python을 이용해서 풀려면 참 난감해진 문제였다. 조합을 잘 짜면, 시간을 넘지않을수도 있지만, 

 

시간초과에 걸리는 경우가 많았다.

 

그래서 조합을 구하는 방식을 비트마스킹을 통해 만들었따. 2**(k)승의 형태로 만들어주고, and 연산을 해서 우리가 만든 조합에 포함되어있는지 아닌지 확인하는 방식이다.

 

from itertools import combinations

N,K = map(int,input().split())
ord_dict = {}

for k in range(26):
    ord_dict[chr(k+97)] = k

K = K - 5
if K <0:
    print(0)
    exit(0)
else:
    origin_word = set(['a','n','t','i','c'])
    word_bit_list = list()
    combination_word = set()
    answer = 0
    for _ in range(N):
        temp = set(list(input())[4:-4]) - origin_word
        if len(temp) == 0:
            answer += 1
        elif len(temp) <=K:
            word_bit = 0
            for w in temp:
                word_bit = word_bit + 2**ord_dict[w]
            word_bit_list.append(word_bit)
            combination_word |= temp

    word_lens = len(combination_word)
    if K > word_lens:
        K = word_lens
    chk_cnt = 0
    for pick_words in combinations(combination_word,K):
        cnt = 0
        temp = 0
        for pick_word in pick_words:
            temp = temp + 2**ord_dict[pick_word]
        for word_bit in word_bit_list:
            if word_bit & temp == word_bit:
                cnt += 1

        chk_cnt = max(chk_cnt,cnt)

    print(answer + chk_cnt)

위의 방식보다 훨씬 빠른 방식이다. 이 방식은 기본적인 컨셉은 비슷하다.

 

하지만 2가지가 다르다.

 

첫번째는 전체 알파벳 26개중에서 K개를 뽑던거에서 고정적으로 들어간 a,c,i,n,t를 무조건 뽑는다고 생각하고,

 

그리고 주어진 단어들에 있는 단어들 중에서 나머지 K-5개를 뽑는것이다.

 

 

두번째는 각 단어들의 BIT를 비교했던것에서 단어 전체의 bit를 저장해준뒤, 우리가 만든 combination bit와 and 연산을해서, 원래 word_bit가 유지되는지 확인을 해주는 방식이다.

 

이러한 방법을 통해 시간을 줄일 수 있다.