[비트연산] 소프티어 lv.3 CPTI [Python]

from collections import Counter

import sys



# 0~2개의 비트만 켜진 수의 목록 생성 (친밀감을 느낄 수 있는 XOR연산 결괏값 사전)

def generate_low_bit_xors(bit_length):

    results = []

    for i in range(bit_length):

        results.append(1 << i) # i번째에 1인 2진수 생성

        for j in range(i + 1, bit_length):

            results.append((1 << i) | (1 << j)) # or 조건으로 i번째와 j번째가 1인 2진수 생성

    results.append(0)  # 0개도 추가

    return results



# 입력

input = sys.stdin.readline

N, M = map(int, input().split(' '))



result = 0



nums = []

for i in range(N):

  nums.append(int(input(), 2))

  

# 카운터로 중복 입력 간소화

counter = Counter(nums)



low_bit_xors = generate_low_bit_xors(M) # 2진수 사전

result = 0

visited = set() # 비교 쌍의 방문 여부 저장 set



for num in counter:

    for x in low_bit_xors:

        # 여기서 x는 2개의 비트만 켜진 수

        # num과 x를 XOR 연산한 결과가 counter에 존재할 경우를 카운트

        target = num ^ x

        if target in counter:

            # 아직 확인되지 않은 조합인 경우

            if (target, num) not in visited:

                if num == target:

                    # 자기 자신이면 조합 수 계산 n * n-1 / 2

                    result += counter[num] * (counter[num] - 1) // 2

                else:

                    # 서로 다른 수인 경우 n * m

                    result += counter[num] * counter[target] 

                # 중복 제거: (num, target)과 (target, num)는 같은 쌍

                visited.add((num, target))



print(result)

 

Java에서 하던 대로

O(N*2) 코드로 했더니 시간초과가 계속 떠서 ChatGPT를 활용해 해결했다.

잘 이해가 안 되는 부분은 주석으로 정리하며 한 줄씩 봤다.

공부 많이 됐다.

 

1. 입력 길이의 비트에서 1이 0~2개인 조합을 먼저 사전으로 저장

2. 입력된 비트값의 리스트를 counter로 중복 개수 파악

3. counter에 있는 비트값(코드 상의 num)을 일일이 사전에 저장된 비트값(코드 상의 x)과 XOR 연산

4. 3에서 나온 결괏값(코드 상의 target)이 counter에 있다면 num과 target의 조합을 처리한 조합으로 visited에 저장

5. num과 target이 같은 값인 경우 n * n -1 / 2 개의 조합 생성

6. num과 target이 다른 값인 경우 n * m 개의 조합 생성