둔필승총

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

[문제 정의]

이 문제는 n개의 단어가 주어지면 k개의 알파벳을 배워서 몇 개나 읽을 수 있는지 판단하는 것이다. 근데 조건에서 단어는 무조건 앞에는 anta로 시작되고 끝은 tica로 끝난다.

해당 조건에서 알 수 있는 사실은 a, c, i, n, t는 최소한 배워야 단어를 읽을 수 있다는 사실이다. 만약에 k가 5보다 작으면 a,c,i,n,t를 다 배우지 못하기 때문에 판단하기도 전에 제외된다. 

[풀이]

먼저, 나는 alreadyLearned변수에 a,c,i,n,t를 집합으로 정의하였다. 그리고 단어를 입력받을때 단어는 무조건 anta로 시작하고 tica로 끝난다고 하였으므로 해당 단어를 잘라서 나머지 부분만 letter에 저장하여 letters에 넣었다. 그리고 toLearnList라는 변수에는 배워야하는 단어들을 다 추가하였다.

 예를 들어 단어가 antacbtica와 antaztica라고 한다면 letter는 [c,b], [z]가 들어가고 toLearnList에는 c,b,z,를 모두 합한 집합인 {c,b,z}가 들어간다. 

그리고 나는 조합을 이용하여서 toLearnList에서 k-5개를 뽑았다. k-5개를 뽑은 이유는 이미 alreadyLearned에 있는 5개는 벌써 배웠다고 가정하는 것이다.

그래서 뽑은 경우의 수를 하나씩 테스트해서 letter에 있으면 continue를 하고 없다면 break를 하는 식으로 반복문을 빠져나와서 조합으로 뽑은 경우의 수마다 몇 개의 단어를 배울 수 있는지 answer에 모두 넣는다. 그래서 answer배열 중 제일 큰 수가 제일 많이 배울 수 있는 경우이므로 해당 값을 출력한다.

 예를 들어 letters로 antartica, antahellotica, antartica를 입력 받은경우 나머지 변수들은 아래와 같다.

[['r'], ['h', 'o', 'e', 'l'], ['r']] # letters
['e', 'h', 'o', 'r', 'l'] # toLearnList
[('o',), ('l',), ('h',), ('e',), ('r',)] # checks

[놓친 부분]

처음에 계속 틀렸었는데 이유를 찾지 못하였다. 같은 스터디원에게 도움을 요청한 결과 combination을 완벽하게 사용하지 못한 것이 이유였다.

1C3과 같은 경우는 combination에서 처리를 하지 못하기 때문에 (1개에서 3개를 뽑는 경우는 되지 않는다) 해당 코드는 오류처리를 해주었어야 하는데 놓쳤었다.

[정답]

import sys

input = sys.stdin.readline
from itertools import combinations


def antarctica(letters, toLearnList):
    # print(letters) [['r'], ['h', 'o', 'e', 'l'], ['r']]
    # print(toLearnList) ['e', 'h', 'o', 'r', 'l']
    if len(toLearnList)<k-5:
        print(len(letters))
    else:
        checks = list(combinations(toLearnList, k - 5))
        # print(checks) # [('o',), ('l',), ('h',), ('e',), ('r',)]
        answer = []
        for check in checks:
            ans = len(letters) # 처음엔 다 배울 수 있다고 가정하고 못배우는 걸 뺴는 방법으로
            check = list(check) # 필요한지 잘 모르겠음
            for letter in letters:
                if len(letter) > k - 5:  # 배워야 되는 숫자가 더 많음
                    ans -= 1
                    continue
                elif len(letter) == 0:  # 이미 다 배움
                    continue
                else:
                    for i in range(len(letter)):
                        if letter[i] in check:  # 조합으로 k-5만큼 선택한 배열 안에 있는 경우
                            continue  # 계속 진행
                        else:
                            ans -= 1  # 없을 경우 이 단어는 이 조합으로는 일단 만들 수 없다
                            break
            answer.append(ans)
        print(max(answer))


n, k = map(int, input().split())
alreadyLearned = {'a', 'c', 'i', 'n', 't'} # 무조건 a,c,i,n,t는 배워야 함. 최소 5개
letters = []  # 가르치는 단어들
toLearnList = set()  # 배워야하는 글자들
for i in range(n):
    letter = set(list(input())[4:-5]) - alreadyLearned  # 입력받은 단어를 앞뒤 다 짜르고 이미 배운거 빼기
    toLearnList.update(letter) # 배워야하는 곳에 추가하기
    letters.append(list(letter))
if k < 5:
    print(0)  # 아무것도 배울 수 없다.
else:
    antarctica(letters, list(toLearnList))

[다른 풀이]

스터디원의 다른 풀이 중 비트마스킹을 사용하는 풀이가 있었다. (다시 봐도 생각해내기는 어려울것 같긴하다..)

비트 마스킹이란 컴퓨터 내부적으로 모든 자료는 이진수로 표현하기 떄문에 이런 특성을 이용해서 이진수 표현을 자료구조로 사용하는 기법을 비트 마스킹이라고 한다. 

비트마스크를 이용하면 집합을 쉽게 표현할 수 있다. 집합에 원소를 추가, 삭제하는 연산을 굉장히 빠르게 할 수 있다. 

원소의 개수가 N인 집합이 있다고 하면, 각각의 원소를 0부터 (N-1)번까지 번호를 부여하고, 번호에 해당하는 비트가 1이면 원소가 포함, 0이면 원소가 불포함이라고 한다면 집합을 비트를 이용해 표현할 수 있다.

이전 풀이는 집합으로 단어를 저장했는데 이번에는 이진법으로 알파벳을 포함하는지 아닌지를 저장하는 차이이다. 

메모리를 훨씬 줄일 수 있어서 더 효율적인 코드인것 같다.

참고 :  https://coder38611.tistory.com/136

from itertools import combinations
n, k = map(int, input().split())
if k < 5:
    print(0)
else:
    k -= 5
    alreadyLearned = {'a', 'n', 't', 'i', 'c'}
    input_chars = []
    alpha = {ky: v for v, ky in enumerate(
        (set(map(chr, range(ord('a'), ord('z')+1))) - alreadyLearned))} # 이미 배운것은 뺴줌
    cnt = 0
    for _ in range(n):
        tmp = 0
        for c in set(input())-alreadyLearned:
            tmp = 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)