💡 문제
남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.
남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.
출력
첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.
💭 접근
우선, 남극언어를 사용하기 위해선 "a, n, t, i, c"는 반드시 배워야하는 알파벳이므로 반드시 5개 이상의 알파벳을 배워야한다.
그리고 이 문제는 비트마스크를 사용하여 해결할 수 있는데, 우선 기본적으로 배워야하는 "a, n, t, i, c"에 대해 비트로 변환해준다.
base_bit = word_to_bit('antic')이때 알파벳의 인덱스를 비트로 변환시켜주는 함수가 필요한데, 바로 word_to_bit 함수이다.
def word_to_bit(word): # 알파벳의 인덱스를 비트로 변환해주는 함수
bit = 0
for s in word:
bit |= (1 << ord(s) - ord('a'))
return bit이 함수를 먼저 살펴보자. 이 함수는 입력받은 단어에 포함된 알파벳의 인덱스만큼 shift 연산을 수행하는 함수이다. 예를 들어 기본 알파벳인 "antic"에 대해 수행시켜보면,
0b10000010000100000101
이렇게 출력되는데, 이는 오른쪽부터 왼쪽으로 a, c, i, n, t의 순서에 해당하는 비트만 1로 표현시켜준다.
이후, 배울 알파벳의 조합을 만들기 위해 먼저 필수로 배워야하는 알파벳을 제외한 알파벳의 list를 만들어 준다.
alph = [1 << i for i in range(26) if not base_bit & 1 << i]이때 alph에는 (0b10, 0b1000, 0b10000, ...)와 같이 "a"(0b1), "c"(0b100)처럼 기본 알파벳을 제외한 나머지 알파벳들이 비트형태로 저장된다.
이후 간단한 dfs 함수를 작성할 수 있는데, 생성하는 조합의 개수는 이다.
def dfs(start, depth, arr): # alph안에 있는 알파벳에서 k - 5개 뽑기
if depth == k - 5:
combs.append(arr[:])
return
for i in range(start, len(alph)):
arr.append(alph[i])
dfs(i + 1, depth + 1, arr)
arr.pop()이제 이렇게 만든 알파벳 조합으로 어떤 조합을 사용했을 때 가장 많은 단어를 배울 수 있는지만 구하면 된다.
for comb in combs:
# 이때 sum 연산도 or 연산과 같음
# 자신의 인덱스를 제외한 모든 비트가 0이기 때문
learned_bit = sum(comb) | base_bit
cnt = 0
for bit in bits:
# and 연산으로 모두 배운 알파벳인지 확인
if bit & learned_bit == bit:
cnt += 1
ans = max(ans, cnt)위 코드를 보면 우선 조합들이 들어 있는 combs 리스트에서 하나의 조합 comb를 뽑으며 입력으로 주어진 단어들과 비교해보면 된다.
이때 learned_bit = sum(comb) | base_bit을 통해 기본 알파벳과 조합에 들어있는 알파벳을 합쳐주고, bit & learned_bit == bit과 같이 and 연산을 통해 입력으로 받은 단어에 들어있는 알파벳의 구성과 일치하는지 비교해준다.
📒 코드
def dfs(start, depth, arr): # alph안에 있는 알파벳에서 k - 5개 뽑기
if depth == k - 5:
combs.append(arr[:])
return
for i in range(start, len(alph)):
arr.append(alph[i])
dfs(i + 1, depth + 1, arr)
arr.pop()
def word_to_bit(word): # 알파벳의 인덱스를 비트로 변환해주는 함수
bit = 0
for s in word:
bit |= (1 << ord(s) - ord('a'))
return bit
n, k = map(int, input().split())
words = [input() for _ in range(n)]
bits = list(map(word_to_bit, words))
base_bit = word_to_bit('antic')
ans = 0
if k >= 5:
# a, n, t, i, c를 제외한 모든 알파벳 저장
alph = [1 << i for i in range(26) if not base_bit & 1 << i]
combs = []
dfs(0, 0, []) # (26 - 5) C (k-5) 조합 생성
for comb in combs:
# 이때 sum 연산도 or 연산과 같음
# 자신의 인덱스를 제외한 모든 비트가 0이기 때문
learned_bit = sum(comb) | base_bit
cnt = 0
for bit in bits:
# and 연산으로 모두 배운 알파벳인지 확인
if bit & learned_bit == bit:
cnt += 1
ans = max(ans, cnt)
print(ans)
💭 후기
비트마스크를 많이 사용해보지 않아서 많이 생소했던 문제였다. 비트마스크도 익숙해질 때까지 많이 연습하자!
🔗 문제 출처
https://www.acmicpc.net/problem/1062
