백준 1062 - 가르침 (python)

평범한 대학생·2023년 2월 8일

baekjoon

목록 보기

2/12

가르침 문제 보러가기

비트마스킹 알고리즘이란? 컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이와 같은 특성을 활용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라고 한다.

비트 연산 종류

& (AND) : 두 비트가 모두 1일때 1반환

| (OR) : 두 비트가 모두 1또는 하나라도 1일때 1반환

^ (XOR) : 대응하는 비트가 서로 다르면 1반환

~ (NOT) : 비트의 값을 반전

<<, >> (시프트연산) : 왼쪽 또는 오른쪽으로 비트를 옮김

문제

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

출력

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

핵심 포인트 요약

어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지
👉 K개의 글자를 가르친다고 할때, K개의 글자와 주어진 단어를 비교하면서 주어진 단어(문자열)을 만들 수 있으면 학생들이 읽을 수 있는 단어가 된다.
즉, 문자열 비교를 비트마스킹으로 하는 것이 핵심이다.
모든 단어는 "anta"로 시작되고, "tica"로 끝난다.
👉 모든 단어에는 'a', 'n', 't', 'i',' c' 라는 문자가 포함되있으며 만약 여기에 있는 5개의 글자(문자)를 가르치지 않으면 학생들은 모든 단어를 읽을 수 없게 된다.
K는 26보다 작거나 같은 자연수 또는 0이다.
👉 단어는 영어 소문자로만 이루어져 있으며, K의 범위에 대한 의미는 글자(문자)를 하나도 안가르칠수도 있고 26개 전부다 가르칠 수 있다는 뜻이다. 영어 알파벳이 총 26개라는것 이용하라는 것임을 알 수 있다.

예제입력 1

3 6
antarctica
antahellotica
antacartica

동작 과정을 추적하기 위해 예제 입력1에 있는 값을 활용했습니다.

코드 & 설명 주석 포함

import sys
from itertools import combinations

input = sys.stdin.readline


def encoding(X):
    return ord(X) - ord('a')


def bitmasking(arr, result=0):
    for i in arr:
        result |= (1 << i)
    return result


N, K = map(int, input().split())

init = set(encoding(i) for i in ('a', 'c', 'i', 'n', 't'))
# 문자를 아스키코드 표에 있는 정수 값으로 인코딩함
# print(init) 		 # {0, 2, 8, 13, 19}

base = bitmasking(init)
# print(base)        # 532741
# print(bin(base))   # '0b10000010000100000101'

data = [set(map(encoding, input().strip())) for _ in range(N)]
# (모든 단어에 대해) 단어를 구성하고 있는 문자 하나하나 정수 값으로 인코딩함
# print(data)         
# [{0, 2, 8, 13, 17, 19}, {0, 2, 4, 7, 8, 11, 13, 14, 19}, {0, 2, 8, 13, 17, 19}]

bin_data = [bitmasking(i) for i in data]
# 인코딩한 정수값을 비트마스킹을 통해 단어에 포함된 문자는 1로 그외에 0으로 표시 
# 2^0~2^25(0부터 25까지)형태로 표현함
# print(bin_data)     # [663813, 551317, 663813]

# 이렇게 표현하면 각각의 단어마다 어떤 문자를 구성해서 단어를 만들었는지 알 수 있음
# for i in bin_data:print(bin(i))
# ['0b10100010000100000101', '0b10000110100110010101', '0b10100010000100000101']
# ['antarctica', 'antahellotica', 'antacartica']


# 후보 글자 선정 (무조건 포함해야하는 문자(init) 제외)
candi = set.union(*data) - init

answer = 0
# K가 5보다 작다면 기본적으로 모든 단어에 들어가는 'a', 'c', 'i', 'n', 't' 글자를 다 배우지 못하게되서
# 읽을 수 있는 단어가 없게 됨
if K < 5:
    pass
# K가 5개가 넘어가면 일단 모든글자에 포함되있는 'a', 'c', 'i', 'n', 't' 글자는 필수로 배워야함
else:
    # 가르칠 (K-5)개의 글자가(필수로 배워야하는 글자를 제외한 숫자가) 후보 글자수 보다 많다면 모든 단어를 다 읽을 수 있음
    if len(candi) <= (K - 5):
        answer = N
    
    # 그렇지 않으면 후보 글자중 (K-5)개를 선택했을때(조합 사용) 제일 많이 읽을 수 있는 글자를 찾아야함
    else:
        for comb in combinations(candi, K - 5):
            tmp = bitmasking(comb, base)
            tmp ^= (1 << 26) - 1                
            # 2^0~2^25 (0부터 25까지 모든 자리를 1로 만든 이진수랑)
            # 후보 문자중 K-5개 문자를 선택해 만든 tmp랑 XOR 연산 수행한 것을 tmp에 저장 --> 같으면 0 다르면 1
            answer = max(answer, sum(1 if (tmp & i) == 0 else 0 for i in bin_data))
            # 비트마스킹된 주어진 단어와 tmp랑 AND연산을 해서 0이 나왔다면 단어가 일치 한다는 의미
            # candi에서 K-5만큼 뽑았던 문자로 단어를 만들 수 있다는 의미로 만들(완성할) 수 있으면 1 없으면 0을 해서 sum연산을 수행
            
print(answer)

코드 & 설명 주석 미포함

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

def encoding(X):
    return ord(X) - ord('a')

def bitmasking(arr, result=0):
    for i in arr:
        result |= (1 << i)
    return result

N, K = map(int, input().split())

init = set(encoding(i) for i in ('a', 'c', 'i', 'n', 't'))
base = bitmasking(init) 

data = [set(map(encoding, input().strip())) for _ in range(N)]  
bin_data = [bitmasking(i) for i in data] 

candi = set.union(*data) - init

answer = 0
if K < 5:
    pass
else:
    if len(candi) <= (K - 5):
        answer = N
    else:
        for comb in combinations(candi, K - 5):
            tmp = bitmasking(comb, base)
            tmp ^= (1 << 26) - 1                   
            answer = max(answer, sum(1 if (tmp & i) == 0 else 0 for i in bin_data))            
print(answer)

보충 설명

def encoding(X):
    return ord(X) - ord('a')

👉 이 함수는 why? 썼는지 그리고 어떤 함수인지

어떤 함수인가?
- ord() 함수는 간단하게 문자를 숫자로 바꿔주는 함수 입니다. 아스키코드 표를 보면 어떤 값으로 바꿔주는지 알 수 있습니다.
  - ord('a')는 10진수로 97
  - ord('z')는 10진수로 122
why 썼는가?
K의 범위가 26까지라고 문제에서 주어진상태에서 ord(x) - ord('a') 값의 범위를 생각해보면 x 값은 영어 소문자만 가능하기 때문에 x 값이 a 일때 0 'z' 일때 25로 매핑되어 0부터 시작해 25까지 총 26개가 됩니다.
이렇게 만든 이유는 배열의 인덱스로 활용하거나 비트마스킹을 할 때 유용하기 때문이라 생각됩니다.

def bitmasking(arr, result=0):
    for i in arr:
        result |= (1 << i)
    return result

👉 함수 설명

정수의 이진 표현을 활용한 비트마스킹 기법입니다.
어떤 문자(요소)로 구성되어 있는지 0과 1로 쉽게 나타낼 수 있습니다. 즉, 사용할 수 있는 문자는 1으로 사용불가능한 문자는 0으로 표시됩니다.
바로 위에서 0부터 시작해 25까지 총 26개로 a 부터 z 까지 표현할 수 있다했는데 이를 비트마스킹을 사용해 $2^0$ ~ $2^{25}$ 형태로 표현할 수 있게 됩니다.

# ex1)
arr = [1, 2, 3, 4, 5]
result = bitmasking(arr)
result = '0b111110' = 62
# 2^1, 2^2, 2^3, 2^4, 2^5 자리가 다 1로 구성된 것을 알 수 있음

# ex2)
ch = ['a', 'b', 'c', 'd', 'e'] 

# --> 인코딩 수행(ord(x) - ard('a'))
encoding_ch = [0, 1, 2, 3, 4]

# --> bin_transform(arr) 수행
result = '0b11111' = 31
# 2^0 : 'a' 자리 : 1
# 2^1 : 'b' 자리 : 1
# 2^2 : 'c' 자리 : 1
# 2^3 : 'd' 자리 : 1
# 2^4 : 'e' 자리 : 1