소프티어

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);
        }
        
        // 전체 친밀감을 느끼는 쌍의 수 계산
        int totalPairs = 0;
        for(int i = 0; i < N; i++) {
            for(int j = i + 1; j < N; j++) {
                // XOR 연산으로 다른 비트 수 계산
                int diffBits = Integer.bitCount(cptiList[i] ^ cptiList[j]);
                
                // 다른 비트가 2개 이하면 친밀감을 느끼는 쌍
                if(diffBits <= 2) {
                    totalPairs++;
                }
            }
        }
        System.out.println(totalPairs);
    }
}

O(NM^2) 버전

import java.io.*;
import java.util.*;


/*
    - 요구사항
        - 최대 두 가지 영역에서만 성격이 다르면 친밀감 느낌
        - 동일, 1개 다름, 2개 다름
        - 서로 친밀감을 느끼는 사람 쌍의 수 계산
        - 사람 쌍은 순서를 고려하지 않음
*/


// 1.089s, 65.86MB
public class Main {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); int M = sc.nextInt();


        int[] cptiList = new int[N];
        HashMap<Integer, Integer> cptiMap = new HashMap<>();
        
        for(int i = 0; i < N; i++){
            cptiList[i] = Integer.parseInt(sc.next(),2);
            cptiMap.put(cptiList[i],cptiMap.getOrDefault(cptiList[i], 0) + 1);
        }


        int ssang = 0;


        HashSet<Integer> checkedCptiSet = new HashSet<>();
        for(final int curCpti : cptiMap.keySet()){
            HashSet<Integer> otherSet = new HashSet<>();
            
            // 1. 동일한 경우
            otherSet.add(curCpti);


            // 2. 한 영역만 다른 경우
            for(int i = 0; i < M; i++){
                final int oneDiffCpti = curCpti ^ (1 << i);


                if(cptiMap.containsKey(oneDiffCpti) && !checkedCptiSet.contains(oneDiffCpti)){
                    otherSet.add(oneDiffCpti);
                }
            }
            
            // 3. 두 영역만 다른 경우
            for(int i = 0; i < M; i++){
                for(int j = i + 1; j < M; j++){
                    final int twoDiffCpti = curCpti ^ ((1 << i) + (1 << j));
    
                    if(cptiMap.containsKey(twoDiffCpti) && !checkedCptiSet.contains(twoDiffCpti)){
                        otherSet.add(twoDiffCpti);
                    }
                }
            }


            // 쌍으로 생성가능한 조합 순회하며 개수 더하기
            for(final int otherCpti : otherSet){
                if(otherCpti == curCpti){
                    int curCptiCnt = cptiMap.get(curCpti);
                    if(curCptiCnt > 1){
                        ssang += (int)((curCptiCnt - 1) + 1) * ((curCptiCnt -1) / 2.0);
                    }
                }else{
                    ssang += cptiMap.get(otherCpti) * cptiMap.get(curCpti);
                }
            }


            checkedCptiSet.add(curCpti);
        }
        
        System.out.println(ssang);
    }
}