s_CPTI

문제

https://softeer.ai/practice/11002

중복제거를 할람면 sorting을행햐ㅏㅁ 걍 돌리는게맞음

답

index + ":" + 숫자 이렇게해서 각각 set을 만들어 차집합으로 하면 어떨까 생각햇지만 그것또한 for문이돌아서안댄다

dif=bin(b ^ tmp)[2:] 자르기도 걸려서 안하는게 좋다..

import sys

n,m = sys.stdin.readline().strip().split(' ') # 사람 수 , 문자열 길이
# <span id="다른게-두개-이하면-친밀감-느낌"></span>다른게 두개 이하면 친밀감 느낌

ans = 2** int(m) - 1
cnt = 0

before = []

for _ in range(int(n)):
    tmp = int(sys.stdin.readline().strip(),2)
    nCnt = 0
    for b in before:
        dif=bin(b ^ tmp).count('1')
        # print(dif,bin(b ^ tmp)[2:])
        if dif < 3 :
            nCnt += 1;
    cnt += nCnt
    # print("cnt",cnt,nCnt)
    # print("----")
    before.append(tmp)

# <span id="printbefore"></span>print(before)
print(cnt)

이렇게 하면 o(n^2 * m) 이다

근데 이렇게 하면안된다 M이 훨씬적으니깐 m을 기준으로 찾아야한다.

ㄹㅇ 답

def count_intimate_pairs(N, M, cptis):
    cpti_count = {} # key는 M길이의 값이고 value는 그게 몇개인지 알려줌
    total_pairs = 0

    for cpti in cptis:
        x = int(cpti, 2)
        count = 0

        # 동일한 CPTI
        count += cpti_count.get(x, 0)

        # 1비트 차이나는 CPTI
        for i in range(M): 
            y = x ^ (1 << i) # 하나씩 바꿔봐요
            count += cpti_count.get(y, 0)

        # 2비트 차이나는 CPTI
        for i in range(M):
            for j in range(i+1, M):
                y = x ^ (1 << i) ^ (1 << j)# 두개씩 바꿔봐요
                count += cpti_count.get(y, 0)

        total_pairs += count
        cpti_count[x] = cpti_count.get(x, 0) + 1 #  몇개있는지 저장,업데이트

    return total_pairs

# <span id="입력-처리"></span>입력 처리
N, M = map(int, input().split())
cptis = [input().strip() for _ in range(N)]

# <span id="결과-출력"></span>결과 출력
result = count_intimate_pairs(N, M, cptis)
print(result)

추가해설

M≤30이므로, 주어진 이진 문자열을 32비트 정수로 저장 가능하며 M비트 정수로 취급할 수 있습니다.

각 사람의 CPTI를 순서대로 순회하며, 현재 사람의 CPTI를 나타내는 이진 문자열을 M비트 정수 xx로 변환한다고 합시다. 그러면 그 사람이 친밀감을 느낄 수 있는 CPTI는 x와 최대 두 위치의 비트가 다른 M비트 정수입니다. 이를 위해 고려할 경우는 다음 세 가지입니다:

1. x와 동일한 값.
2. x와 한 개의 비트에서만 차이가 나는 값.
3. x와 두 개의 비트에서 차이가 나는 값.

이 값들이 사람들의 CPTI 목록에서 이전에 등장한 횟수를 전부 더하면 현재 사람이 친밀감을 느끼는 사람의 수를 구할 수 있습니다. 등장 횟수를 효율적으로 구하고 저장하기 위해 HashMap이나 TreeMap을 사용합니다.

2번, 3번에 해당하는 값들 모두 bitwise XOR 연산을 사용해 각각 O(M)O, O(M^2)에 순회할 수 있습니다. 최종 시간 복잡도는 선택한 자료 구조에 따라
O(N * M^2 ) 또는 O(N* M^2 * logN) 이 됩니다.

한 가지 주의할 점은 각 사람에 대해 O(M2)O(M2)개의 후보들의 등장 횟수를 Map에 저장하는 방식으로 문제를 풀 경우 Map의 원소의 크기가 너무 커져서 시간/메모리초과가 발생하게 됩니다. 따라서 각 단계에서 xx의 등장 횟수만 Map에 누적해야 합니다.