[소프티어] CPTI

https://softeer.ai/practice/11002

문제

코드런 나라에는 총 N명의 사람이 살고 있습니다. 이 나라에는 사람들의 성격을 나타내는 CPTI(CodeRun Person Type Indicator)라는 지표가 존재합니다.

CPTI는 길이 M의 이진 문자열로 표현되며, 각 자리의 값은 해당 성격 영역에 대해 그 사람이 긍정형(1)인지 부정형(0)인지를 나타냅니다. 예를 들어, 성격 영역이 세 개인 경우, 첫 번째와 세 번째 지표가 긍정형이고 두 번째 지표가 부정형이라면, 101으로 표현됩니다.

두 사람의 CPTI를 비교했을 때, 최대 두 가지 영역에서만 성격이 다르면 두 사람은 친밀감을 느낀다고 합니다. 예를 들어, M=3인 경우, CPTI가 각각 000, 101인 사람들은 성격이 다른 영역이 2개이므로 친밀감을 느낍니다. 그렇지만, CPTI가 각각 010, 101인 사람들은 세 개의 영역 모두에서 성격이 모두 다르므로, 친밀감을 느끼지 않습니다.

코드런 나라의 왕인 James는 이 나라에 살고 있는 사람들 중에서 서로 친밀감을 느끼는 사람 쌍이 얼마나 되는지 알고 싶어합니다.

James를 위해 서로 친밀감을 느끼는 사람 쌍의 수를 계산하는 프로그램을 작성하세요. 사람 쌍의 경우 순서를 고려하지 않습니다.

문제 제약 조건

[조건 1] 1≤N≤30,000

[조건 2] 1≤M≤30

문제 풀이

1. 비트마스킹+해시맵을 이용
   이건 실수인데 N이 30,000이기 때문에 N!로 반복문 돌린다고 생각했기 때문...
   해시맵으로 반복 시간을 줄여야겠다 ! 생각했는데 생각보다 복잡해지는 코드
2. 비트마스킹을 이용
   이중 반복문을 돌리면 N^2이기 때문에 충분하구나 생각함
   여기서 킥은

• Integer.parseInt(cpti, 2); -> 이진수를 10진수로 변경해서 저장
• Integer.bitCount(cptiList[i] ^ cptiList[j]);
  • Integer.bitCount : 1이 몇개인지 반환
  • ^ : 두 수 다르면 1, 같으면 0인 XOR

느낀점

위에 적은 두 가지 킥을 잊기 싫어서 글을 작성하게 되었다.
알면 비트마스킹에서 유용하게 사용할 수 있을 듯하다.

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] cptiList = new int[N];
        for(int i = 0; i < N; i++) {
            String cpti = br.readLine();
            cptiList[i] = Integer.parseInt(cpti, 2);
        }
        
        int totalPairs = 0;
        for(int i = 0; i < N-1; i++) {
            for(int j = i + 1; j < N; j++) {
                int diffBits = Integer.bitCount(cptiList[i] ^ cptiList[j]);
                if(diffBits <= 2) {
                    totalPairs++;
                }
            }
        }
        
        System.out.println(totalPairs);
    }
}