백준 1062번: 가르침 python 풀이 및 정답 코드

문제 링크

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

1062번: 가르침

 

 

문제 설명

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

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

 

 

 

문제 풀이

이건 사실 구글링을 좀 했다...

브루트포스 방식으로 푸는 비트마스킹 문제라는데 뭔지 몰라서 찾아봤다.

*브루트포스

brute: 무식한, force: 힘   무식한 힘으로 해석할 수 있다.
완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.
이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.

*비트마스크

비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 
정수의 이진수 표현을 자료 구조로 쓰는 기법
을 말한다

검사해야할 알파벳을 비트연산을 통해 비트마스킹으로 표현하고 카운트한다.

 

코드

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

def convert(x):
    return ord(x) - ord('a')

def convert_2(arr):
    result = 0
    for a in arr:
        result |= (1 << a)
    return result

n, k = map(int, input().split())
s = set([convert(a) for a in ['a', 'c', 'i', 'n', 't']])
base = 0
for i in s:
    base |= (1 << i)
arr = [set(map(convert, input().strip())) for _ in range(n)]
arr_2 = [convert_2(a) for a in arr]
candidates = set().union(*arr) - s
answer = 0
if k < 5:
    print(0)
else:
    if len(candidates) <= (k - 5):
        print(n)
    else:
        for c in combinations(candidates, k - 5):
            temp = base
            for i in c:
                temp |= (1 << i)
            temp ^= (1 << 26) - 1
            answer = max(answer, sum(1 if (temp & a) == 0 else 0 for a in arr_2))
        print(answer)

 

 

결과

 

 

 

다른 사람의 코드

 

 

 

리뷰