[Python/파이썬] 소프티어 CPTI

https://softeer.ai/practice/11002

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
cptis = dict()
for _ in range(n):
    input_cpti = int(input(), 2)
    if input_cpti in cptis:
        cptis[input_cpti] += 1
    else:
        cptis[input_cpti] = 1

answer = 0
for num in cptis.keys():
    answer += (cptis[num]*(cptis[num]-1))//2
    # 1개 다른 사람 세기
    for i in range(m):
        new_num = num ^ (1 << i)
        if new_num > num and new_num in cptis:
            answer += cptis[num] * cptis[new_num]
        # 2개 다른 사람 세기
        for j in range(i+1, m):
            new_num2 = new_num ^ (1 << j)
            if new_num2 > num and new_num2 in cptis:
                answer += cptis[num] * cptis[new_num2]

print(answer)

 

시간 복잡도 줄이는게 어려웠던 문제....정답 풀이를 설명하자면 다음과 같다.

 

1. 입력받은 cpti들을 cptis라는 dict에 저장한다. dict에 중복되는 cpti들은 개수만 카운트해서 value로 저장해두면 중복연산을 줄일 수 있다.

2. cptis에 저장되어 있는 key들이 바로 입력된 cpti들이다. 각 cpti에서 1개 또는 2개만 바꿨을 때 cptis에 저장되어 있는 다른 cpti와 겹치는지 확인한다. XOR 연산을 사용하면 특정 비트만 바꾸는 것이 가능하다.

 

이전 풀이(점수: 30/100)

이 정답 풀이를 찾기 전에는 아래와 같이 입력된 CPTI들을 2개씩 쌍을 만들고, 2개 이하의 영역에서 다른 쌍이 몇 개인지 찾는 방식으로 풀이했다.

from itertools import combinations
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
cptis = dict()
for _ in range(n):
    input_cpti = int(input(), 2)
    if input_cpti in cptis:
        cptis[input_cpti] += 1
    else:
        cptis[input_cpti] = 1


def kernighan(num):
    count = 0
    while num:
        num &= (num-1)
        count += 1
    return count


answer = 0
for a, b in combinations(cptis.keys(), 2):
    answer += cptis[a]*cptis[b] if kernighan(a ^ b) <= 2 else 0

# 동일한 CPTI 보유자들
for count in cptis.values():
    if count >= 2:
        answer += (count*(count-1))//2
print(answer)

 

이것도 최대한 시간을 줄여본 코드인데, 점수를 30/100까지만 받을 수 있었다. 여기서 시간을 줄이기 위해서 해봤던 것들은:

1. `dict`를 사용해서 입력된 CPTI 중 중복되는 것들은 연산을 여러 번 하지 않도록 하기

2. 원래 CPTI 두 개의 XOR 연산 결과에서 1의 개수를 셀 때 `bin(xor).count("1")`로 문자열로 만들어서 "1"의 개수를 카운트하는 방식을 사용했는데, 2진수에서 1의 개수를 세는 알고리즘인 kernighan이 있다고 해서 이를 도입해보기

 

근데 결국 이렇게 해도 N이 최대 30,000개인데 이것을 combinations로 묶는 방식을 사용하기 때문에 시간 초과를 피할 수 없었던 것 같다. 그래서 위에 나온 정답 풀이와 같이 2개씩 쌍을 짓지 않고도 해결할 수 있는 방식으로 변경했다.

내가 이전에 사용했던 방식의 시간 복잡도가 O(N^2*M)인 반면, 정답 풀이의 시간 복잡도는 O(N*M^2)이다. 이 문제는 M에 비해 N이 훨씬 크기 때문에 O(N*M^2)가 유리하다.

 

🔗 참고 자료

1. https://blog.advenoh.pe.kr/algorithm-%EC%A0%95%EC%88%98%EA%B0%92%EC%97%90%EC%84%9C-1%EC%9D%B4-%EC%84%A4%EC%A0%95%EB%90%9C-bit%EB%A5%BC-%EC%B9%B4%EC%9A%B4%ED%8A%B8%ED%95%98%EA%B8%B0/#22-Approach-2---Brian-Kernighans-Algorithm

2. https://softeer.ai/connect/devtalk/1801