[백준] 1062 가르침 파이썬

문제

https://www.acmicpc.net/problem/1062

1062번: 가르침

 

---

풀이

공통으로 포함되는 알파벳 a c n t i를 제외하고

중복을 없애기 위해 set으로 각 단어를 읽기 위해 추가로 필요한 알파벳들을 구한다.

그 다음 전체 알파벳에서 a c n t i 를 제외한 k-5개의 조합을 만들어

각 조합별로 몇 개의 단어를 읽을 수 있는지 세려고 했다.

 

그런데 조합 만들어서 테스트하는 부분에서 연산이 엄청 많이 시행될 것 같았다.

뭔가 시간초과의 느낌이 나서 다른 분의 풀이를 먼저 보았다.

 

앞에서 말한 단계까지는 동일했으나 예상했던대로 조합별로 몇 개의 단어를 읽을 수 있는지 세는 부분에서

시간초과가 뜬다고 한다.

 

결론은 비트마스크를 써야한다고 한다.

카카오 코테에서도 그렇고 비트마스크 문제를 꽤나 많이 봤었다.

이참에 공부해두자 싶어서 풀려고 하는데 다른 분들의 풀이를 안 보기엔 너무 어려웠다ㅎ

 

from sys import stdin
from itertools import combinations


# bin_dict : a/c/i/t/n을 제외한 알파벳 각각에 임의의 고유 번호를 부여한 딕셔너리
bin_dict = {'b': 20, 'd': 19, 'e': 18, 'f': 17, 'g': 16, 'h': 15, 'j': 14,
            'k': 13, 'l': 12, 'm': 11, 'o': 10, 'p': 9, 'q': 8, 'r': 7,
            's': 6, 'u': 5, 'v': 4, 'w': 3, 'x': 2, 'y': 1, 'z': 0}


# 알파벳 배열을 2진수로 바꾸어주는 함수
def word_to_bin(word):
    answer = 0b0
    for x in word:
        answer = answer | (1 << bin_dict[x])

    return answer


n, k = map(int, stdin.readline().split())
words = []
# 각 입력 단어에 대하여
# 1. 앞의 anta와 뒤의 tica를 슬라이스한 뒤 set로 만들고
# 2. 그중 a/c/i/t/n을 제외한 뒤 words 리스트에 저장
for _ in range(n):
    words.append(set(stdin.readline().rstrip()[4:-4]).difference('a', 'c', 'i', 't', 'n'))

# k가 5 미만이라면 어떤 단어도 만들 수 없음.
if k < 5:
    print(0)
else:
    bin_list = [word_to_bin(x) for x in words]
    max_count = 0

    # 2의 0제곱부터 2의 20제곱까지 저장한 리스트
    power_of_2 = [2 ** i for i in range(21)]

    # 현재 순회 중인 k - 5개의 알파벳 조합(comb)으로
    for comb in combinations(power_of_2, k - 5):
        current = sum(comb)
        count = 0
        for bin_number in bin_list:
            # 현재 순회 중인 단어를 만들 수 있다면
            if bin_number & current == bin_number:
                # count에 1을 더한다.
                count += 1

        # count = comb로 만들 수 있는 단어의 개수
        max_count = max(max_count, count)

    print(max_count)

출처:

https://velog.io/@ready2start/Python-%EB%B0%B1%EC%A4%80-1062-%EA%B0%80%EB%A5%B4%EC%B9%A8

[Python] 백준 - 1062 가르침

비트마스크를 떠올리는 것과 &연산을 쓰기 위한 많은 전처리 과정을 할 수 있는지 묻는 문제 같았다.

 

from itertools import combinations

n, k = map(int, input().split())
if k < 5:
    print(0)
else:
    k -= 5
    nece_chars = {'a', 'n', 't', 'i', 'c'}
    input_chars = []
    alpha = {ky: v for v, ky in enumerate(
        (set(map(chr, range(ord('a'), ord('z')+1))) - nece_chars))}
    cnt = 0
    for _ in range(n):
        tmp = 0
        for c in set(input())-nece_chars:
            tmp |= (1 << alpha[c])
        input_chars.append(tmp)
    power_by_2 = (2**i for i in range(21))
    for comb in combinations(power_by_2, k):
        test = sum(comb)

        ct = 0
        for cb in input_chars:
            if test & cb == cb:
                ct += 1

        cnt = max(cnt, ct)
    print(cnt)

https://coder38611.tistory.com/136

[백준 1062번-파이썬/Python] 가르침

이 분 코드는 전처리 과정이 넘 깔끔해서 가져왔다.

이 분 코드 거의 따라쳐서 통과했다.

 

from itertools import combinations

n, k = map(int, input().split())

if k < 5:
    print(0)
else:
    k -= 5
    base = {'a', 'c', 'n', 't', 'i'}
    alpha = {key: val for val, key in enumerate(
        set(map(chr, range(ord('a'), ord('z')+1))) - base
    )}

    words = []
    for _ in range(n):
        tmp = 0
        for c in (set(input())-base):
            tmp |= (1 << alpha[c])
        words.append(tmp)
    power_by_2 = (2**i for i in range(21))

    answer = 0
    for c in combinations(power_by_2, k):
        test = sum(c)
        ct = 0
        for w in words:
            if test & w == w:
                ct += 1
        answer = max(ct, answer)
    print(answer)

 

 

 

++) 2021.12.23 다시풀어봄

import sys
from itertools import combinations
input = sys.stdin.readline

n, k = map(int, input().split())
if k < 5:
    print(0)
    sys.exit()
k -= 5

base = {'a', 'c', 'n', 't', 'i'}
words = [set(input()[:-1]) - base for _ in range(n)]

alphaset = {k: v for v, k in
        enumerate(set(map(chr, range(ord('a'), ord('z')+1))) - base)}

bitwords = []
for wordset in words:
    bitword = 0
    for w in wordset:
        bitword |= (1 << alphaset[w])
    bitwords.append(bitword)

powerby2 = [2**i for i in range(21)]
maxcnt = 0
for c in combinations(powerby2, k):
    test = sum(c)
    cnt = 0
    for b in bitwords:
        if b & test == b:
            cnt += 1
    maxcnt = max(maxcnt, cnt)

print(maxcnt)