소프티어

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)) # ...

파이썬 - 비트연산으로..

스트링으로 했더니 타임아웃 떠서 정수로 바꾸고 비트연산으로 했더니 겨우 통과했네요.. import sys def countEqualPairs(values): countMap = {} for value in values: countMap[value] = countMap.get(value, 0) + 1 result = 0 for count in countMap.values(): result += (count * (count - 1)) // 2 return result def countEqualPairsFrom2(values1, values2): countMap = {} for value in values1: if value in countMap: countMap[value][0] += 1 else: ...

이거 파이썬은 시간초 더 주셔야 할 것 같아요 ㅠㅠ

import sys from collections import defaultdict # N : 사람 수, M : 문자열 길이 N, M = map(int, sys.stdin.readline().split()) cpti = [int(sys.stdin.readline().rstrip(), 2) for _ in range(N)] # 키가 없어도 기본값 0으로 할당 dct = defaultdict(int) same_pair = 0 for i in range(N): same_pair += dct[cpti[i]] # 이전의 사람 중 똑같은 cpti를 가진 사람의 수 만큼 쌍을 더해줌 # 비트 1개 반전 시키는 용도 for j in range(M): # 모든 수와 0의 xor 연산은 자기 자신이 됨 # 따라서 반전 시키고 싶은 비트에 1을 두면 그 자리의 수가 반전 됨 new_cpti = cpti[i] ^ (1 << j) # 한 가지 영역이 다른 cpti same_pair += dct[new...

[CPTI] 타임아웃 기준을 못맞추겠어요

import sys input = sys.stdin.readline N, M = map(int, input().strip().split()) people = [int(input().rstrip(), 2) for _ in range(N)] ans = 0 for i in range(N-1): p1 = people[i] for j in range(i+1, N): if bin(p1^people[j])[2:].count('1') < 3: ans += 1 print(ans) 3초 기준에 3.08x 초로 계속 실패하는데 어떻게 해도 실패하네요. O(N^2M) 보다 더 빠르게 못할 것 같은데.

java 정답 코드

O(N^2) 버전 import java.util.*; // 1.982s , 31.03MB public class Main_N_Squre {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int N = sc.nextInt();         int M = sc.nextInt();                 // CPTI 입력 받기         int[] cptiList = new int[N];         for(int i = 0; i < N; i++) {             String cpti = sc.next();             cptiList[i] = Integer.parseInt(cpti, 2);         }                 // 전체 친밀감을 느끼는 쌍의 수 계산     ...