[python] 백준 1062 - 가르침

출처 : 백준, https://www.acmicpc.net/problem/1062

1062번: 가르침

 

# n개의 단어가 있고 k개의 글자를 가르칠 거임
# 모든 단어는 anta로 시작하고, tica로 끝남.
# 단어 내의 모든 글자를 알고 있다면 단어를 읽을 수 있음.
# 1 <= n <= 50
# 1 <= k <= 26
# 영어 단어는 소문자로만 구성, 8 <= 길이 <= 15

# 학생들이 읽을 수 있는 단어 개수의 최댓값

 

 

먼저, 생각해야 할 부분

 

1. a, n, t, i, c는 꼭 가르쳐야한다. 즉, 단어를 1개 이상 읽게 하기 위해서는 글자를 최소 5개는 가르쳐야한다.
     전체 글자 집합에서 a, n, t, i, c를 제외하고 k - 5개를 골라서 가장 많이 읽을 수 있는 단어의 수를 구해야 한다.

---

 

풀이

 

사실 그냥 집합 써도 풀리는 줄 몰라서 비트마스킹으로 풀었는데, 그냥 집합 써도 풀리더라...충격과 공포

처음에 왜 안 풀린건가 했더니 부분 집합 판별 연산을 교집합과 일치 연산자로 사용했기 때문...

대소비교 연산자로 하면 통과된다.

from itertools import combinations

def solution(n, k, word_list):
    TEACH_COUNT = k - 5

    except_set = set(['a', 'c', 'i', 'n', 't'])

    word_set_list = []
    union_set = set()
    
    # word_set 만듬.
    for word in word_list:
        word_set = set(word) - except_set
        word_set_list.append(word_set)
        union_set |= word_set

    if TEACH_COUNT < 0: #가르칠 수 있는 글자가 없음
        return 0

    if len(union_set) <= TEACH_COUNT: #모든 단어를 가르칠 수 있음
        return n

    max_val = 0

    for combi in combinations(union_set, TEACH_COUNT):
        count = 0

        for word_set in word_set_list:
            if word_set <= set(combi): #대소비교를 사용하지 않고 교집합 + 일치 사용 시 시간 초과
                count += 1

        max_val = max(max_val, count)

    return max_val

n, k = map(int, input().split())
word_list = [input() for _ in range(n)]

print(solution(n, k, word_list))

 

비트 마스킹을 이용한 풀이

 

완전 탐색 시 비트마스킹을 이용해 탐색 시간을 줄이는 풀이이다.

정확히는 집합 연산 시간을 비트마스킹으로 줄여서 통과하는 풀이다.

위의 풀이보다 확실히 빠르다.

from itertools import combinations

def solution(n, k, word_list):
    # 제외 글자
    except_char_set = set(['a', 'c', 'i', 'n', 't'])

    union_set = 0b0
    union_char_set = set()
    word_set_list = []

    for word in word_list:
        word_set = 0b0

        for char in word:
            if char in except_char_set:
                continue

            word_set |= 1 << (ord(char) - 96)
            union_char_set.add(char)

        word_set_list.append(word_set)

        union_set |= word_set

    TEACH_COUNT = k - 5

    # 가르칠 수 있는 글자가 없다.
    if TEACH_COUNT < 0:
        return 0

    # 모든 글자를 다 가르칠 수 있다.
    if len(union_char_set) <= TEACH_COUNT:
        return n

    # 글자 조합에 대해서 몇개의 글자를 배울 수 있는지 반복한다. -> 최댓값 갱신
    # 전체 글자 집합에서 k - 5개를 뽑는다.
    max_val = 0

    for combi in combinations(union_char_set, TEACH_COUNT):
        count = 0
        combi_set = 0b0

        for char in combi:
            combi_set |= 1 << (ord(char) - 96)

        for word_set in word_set_list:
            if word_set & combi_set == word_set:
                count += 1

        max_val = max(max_val, count)

    return max_val

n, k = map(int, input().split())
word_list = [input() for _ in range(n)]

print(solution(n, k, word_list))

---

알게 된 점

 

combinations의 함정

 

from itertools import combinations

combinations([1, 2, 3, 4], 5)  # []

 

파이썬의 combinations 모듈은 파라미터로 iterable한 객체와 뽑을 개수를 받는다.

그런데 만약 iterate한 객체의 길이보다 뽑아야하는 갯수가 많다면 빈 리스트를 리턴한다.

이는 조합의 코드화에서 작성한 코드에서도 동일하게 발생한다.

 

따라서, combinations 모듈 사용 시 뽑는 개수가 iterable한 객체의 길이보다 커지지 않도록 주의해야한다.

이는 순열에서도 동일하다.

 

문자열을 집합으로

 

set('abc')      # {'a', 'b', 'c'}
set(['abc'])    # {'abc'}

 

단어를 그대로 set 함수에 넣으면 각 문자를 원소로 하는 집합이 만들어진다. 

단어들의 집합을 만들고 싶다면, 리스트에 단어를 추가해서 넣어준다.

 

집합의 대소비교

 

a = set([1, 2, 3])
b = set([1, 2])
c = set([1, 2, 4])

print(b < a)    # True
print(c < a)    # False

 

집합은 기본 자료형이다. 따라서 <, <=, >, >=을 통한 대소 비교가 가능하다.

이를 이용하면 A가 B의 부분집합인지 쉽게 판별할 수 있다.

이 연산은 교집합과 일치 연산자를 활용한 연산보다 빠르다.

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들

 

Reference

python combinations 사용 시 유의사항 알려드립니다.