[Softeer] CPTI 풀이 - 파이썬

첫 알고리즘 관련 글이기에 서두를 조금 길게 하자면,

코딩 문제를 풀 때 가장 중요한 것은 문제를 정확하게 이해하는 것

문제의 본질은 간단하지만, 불필요한 설명이 많아 핵심을 놓치기 쉬운 경우가 많습니다.

문제

문제의 본질:
길이 M인 이진 문자열 N개가 주어졌을 때, 두 문자열 간 다른 비트의 개수가 2 이하인 경우를 찾는 문제입니다.

제약 조건

• 1≤N≤30,000

• 1≤M≤30

• Subtask1 (12점): N≤1,000, M≤10

• Subtask2 (18점): M≤10

• Subtask3 (70점): 문제 조건 외에 별도의 제한이 없음

---

XOR에 대하여

이 문제는 비트 연산자(XOR)를 이해하고 활용하는 것이 핵심입니다.
XOR, ⊕, ^ 연산은 두 값이 다르면 1, 같으면 0을 반환합니다.

XOR 연산 예시

x	y	x⊕y
1	0	1
0	0	0
0	1	1
1	1	0

XOR의 주요 특징 및 활용 사례

해석	의미
불일치 검출	x,y 두 값이 다르면 1, 패리티 체크, 에러 검출, 비트 비교 등에 사용
토글 기능	y에 1을 넣으면 값을 뒤집는다. 비트 반전 연산에 사용
캐리 없는 덧셈	이진수에서 XOR은 캐리 없는 덧셈 역할 - 회로에서 중요 (빠른 덧샘연산)
x ⊕ x = 0	배열에서 한 번만 등장한 요소 찾기 문제를 O(N) (전부 xor 해버리면된다)
값 교환	임시 변수 없이 a와 b를 바꿈 (a ⊕ b) ⊕ b = a
비트 마스킹	특정 비트만 조작 가능

(xor은 교환법칙과 결합법칙이 성립합니다)

이 문제에서는 비트 마스킹의 일부인 토글 기능을 활용합니다.

---

풀이

핵심 아이디어

"CPTI에서 최대 2개의 비트가 다른 경우를 빠르게 찾기 위해 비트 마스크를 생성한다."

import sys
from collections import defaultdict

# 비트가 1인 개수를 세는 함수 (최대 2개까지만 체크)
def bit_count2(num):
    answer = 0
    while num:
        num &= (num - 1)  # 최하위 1비트를 제거
        answer += 1
        if answer >= 3:  # 3개 이상 다르면 필요 없음
            return False
    return True

위 함수는 비트 1의 개수가 적을 때 가장 빠르게 동작합니다.
직접 11001 같은 숫자로 테스트해 보면, 최하위 1을 버퍼로 사용하여 앞의 숫자를 유지하는 방식임을 알 수 있습니다.

    11001 & 11000 = 11000
→ 11000 & 10111 = 10000
→ 10000 & 01111 = 00000

다른 비트 카운트 방식

방법	시간복잡도
bin().count('1')	O(log N)
Brian Kernighan’s Algorithm	O(k) (k = 1의 개수) 위의 방식
bit_count() (Python 3.10+)	O(1) (하지만 3.10 미만에서는 사용 불가)
Lookup Table	O(1) (8비트(256개) 미리 계산 후 활용)
Parallel Bit Counting	SIMD 스타일

Parallel Bit 경우 한번 찾아 보시는 것도 좋아요

이제 본격적으로 비트 마스킹을 이용한 해결 방법을 구현 해봅시다.

input = sys.stdin.readline
N, M = map(int, input().split())  # N: 사람 수, M: CPTI 문자열 길이

# 사람들의 CPTI 값을 저장하는 딕셔너리 (각 이진값의 등장 횟수 저장)
count = defaultdict(int)

# 입력받은 CPTI 문자열을 이진수로 변환 후 카운트
for _ in range(N):
    s = input().strip()
    people = int(s, 2)  # 문자열 s를 2진수로 변환
    count[people] += 1  # 해당 CPTI 값의 등장 횟수 증가

# XOR 연산을 위한 비트 마스크 생성
bit_mask = []
for i in range(M):  # 한 개의 비트만 바꿀 경우
    bit_mask.append(1 << i)  # 2^i 위치의 비트만 변경
    for j in range(i + 1, M):  # 두 개의 비트를 바꿀 경우
        bit_mask.append((1 << i) | (1 << j))  # 2^i, 2^j 위치의 비트를 변경

answer = 0  # 친밀한 쌍의 개수

# 각 CPTI 값에 대해 친밀한 관계를 계산
for cpti in count.keys():
    now_people = count[cpti]  # 현재 CPTI를 가진 사람 수

    # 같은 CPTI를 가진 사람들끼리 쌍을 이룸 (조합 nC2)
    answer += now_people * (now_people - 1) // 2

    # XOR을 사용하여 최대 2개 차이나는 CPTI 탐색
    for mask in bit_mask:
        next_cpti = mask ^ cpti
        if next_cpti >= cpti:
            continue
        if next_cpti in count:
            answer += count[next_cpti] * now_people

print(answer)  # 최종 결과 출력

---