[백준/Python] #1062번 가르침

문제 

• 읽을 수 있는 단어 개수가 최대가 되는 K개의 글자 찾기
• 모든 단어는 "anta"로 시작되고, "tica"로 끝난다.
• 남극언어에 단어는 N개 밖에 없다고 가정

<입력 조건>
- N <= 50인 자연수
- K <= 26인 자연수 or K = 0
- 단어: 영어 소문자, 8 <= 단어의 길이 <= 15, 중복 X

 

해결 방법

• 모든 단어에는 앞, 뒤로 무조건 와야하는 문자가 있으므로 'antic'은 무조건 K개의 글자에 포함되어야 한다. 따라서 K의 값이 5보다 작다면 정답은 0이고, 알파벳은 총 26글자 이므로 K의 값이 26이라면 정답은 N이다.
• itertools의 combinations를 사용하여 K-5개로 이뤄진 단어의 조합들을 탐색하며 읽을 수 있는 단어의 최댓값을 업데이트 해주면 된다.
• 단, 여기서 중요한 최적화 포인트는 비트 마스크 연산이다.(처음에는 집합을 이용해 포함 여부를 판별했지만, 시간 초과가 발생했다..)
  
  • 'a'는 0번째 비트 → '1 << 0' → 0b000...0001
  • 'b'는 1번째 비트 → '1 << 1' → 0b000...0010
  이런 방식으로 단어를 나타내면, 각 단어를 하나의 정수(비트마스크)로 표현할 수 있고, 시간 복잡도를 대폭 줄일 수 있어 효율적인 탐색이 가능

 

정답

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

def cal(words, N, K):
    if K < 5:
        return 0
    elif K ==26:
        return N
    
    max_cnt = 0
    target = [1 << i for i in range(26)]
    for i in [ord(ch) - ord('a') for ch in 'antic']:
        target.remove(1 << i)
    
    for combi in combinations(target, K-5):
        cnt = 0
        base = sum(1 << (ord(c) - ord('a')) for c in 'antic')
        
        for c in combi:
            base += c
        for w in words:
            if base & w == w:
                cnt += 1
        max_cnt = max(max_cnt, cnt)
        
    return max_cnt 

def main():
    N, K = map(int, input().split())
    words = []
    for _ in range(N):
        w = 0
        for i in list(input().rstrip()):
            # 비트마스크 형태로 변환 (알파벳을 숫자로 변환 후 해당 위치에 비트를 1로 만듦)   
            # a -> 0 -> 0b000...0001, b -> 1 -> 0b000...0010
            w |= (1 << (ord(i) - ord('a')))
        words.append(w)
    
    print(cal(words, N, K))

if __name__ == "__main__":
    main()