백준 1062 (python)

백준 1062 python 문제풀이

---

회고

---

• 비트 마스킹을 활용한 집합 연산을 알게 되었음
• brute force 알고리즘 (완전탐색) 유형 ->
  • DFS등 그래프 완전탐색
  • combination 같은 조합 완전탐색
• 중복 된 문자라는 키워드를 보고 set으로 접근하였지만, 시간/공간 복잡도에 걸림

풀이

---

풀이는 순서대로 주요 포인트 코드 해석을 위주로 작성

1. 모든 조합을 다 순회해야한다 -> itertools 의 combination
2. 기본적으로 {a, n, t, i, c} 다섯 문자는 무조건 포함이 되므로 5이하의 문자를 배우는 경우는 읽을 수 없음 print(0)
3. 입력받은 K(개수)에서 문자 5개(a, n, t, i, c)를 제외 시킴 5개는 무조건 배워야 하니까.
4. ky(key)와 v(value)를 enumerate를 통해 매칭 ( k에 enum v에 ord(), (아스키코드) 매칭 거기에 이미 존재하는 elements(a, n, t, i, c)의 개수를 뺌
5. 입력받은 단어의 개수 N번만큼 for문을 순회. tmp는 각 단어의 비트 집합 표현을 나타내어 words에 넣기 위한 임시 변수
   1. set(input()) -elements: 는 입력받은 문자에 무조건 포함되는 elements(a, n, t, i, c)를 뺀 문자들을 순회 ex) antarctica -> {r, c} 를 순회
   2. r에 맞는 key를 찾아서 tmp에 맞는 벨류의 원소를 저장
      1. ex) {r, c} 를 순회하고 ‘r’: 2이고 ‘c’: 4이면
      2. 차례대로 tmp에 0b100 (‘r’ : 2), 0b1000 (‘c’ : 4)가 += 되기 떄문에 0b1100이 저장됨
   3. 첫번째 단어의 알파벳 원소의 정보를 담고있는 집합 bin을 words에 저장함(elements를 제외한) 위 예시는 0b1100이 저장 됨
   4. 각 단어 마다 반복
6. bin2char에 2^0 ~ 2^20까지의 수를 저장
7. combinations를 통해 2 ^ N 중에서 K-5개를 선택
8. 나온 조합의 합 (temp = sum(combi)) 이 새롭게 배운 알파벳을 의미
9. words 를 돌면서 temp &(and연산) words의 원소를 하게되면 words의 원소가 temp (모든 조합의 합)에 포함이 되어 있으면 ct를 1 증가
10. ct와 저장되어있는 count를 비교하여 더 많은 조합을 만들 수 있는 최대값이 정답

    코드

---

# 가르침

from itertools import combinations

N, K = map(int, input().split())

if K < 5:
    print(0)
else:
    K -= 5
    elements = {'a', 'n', 't', 'i', 'c'}
    words = []
    count = 0

    dic = {ky: v for v, ky in enumerate(
        (set(map(chr, range(ord('a'), ord('z') + 1)))) - elements)}

    for _ in range(N):
        tmp = 0
        for c in set(input())-elements:
            tmp |= (1<<dic[c])
        words.append(tmp)

    bin2char = (2**i for i in range(21))  # 26(알파벳 총 개수) - 5(무조건 배워야하는 알파벳 antic 개수)

    for combi in combinations(bin2char, K):
        temp = sum(combi)

        ct = 0
        for cb in words:
            if temp & cb == cb:
                ct += 1

        count = max(count, ct)
    print(count)

Ref

---

• https://coder38611.tistory.com/136
• https://velog.io/@ready2start/Python-%EB%B0%B1%EC%A4%80-1062-%EA%B0%80%EB%A5%B4%EC%B9%A8