[Softeer/비트마스크] CPTI

문제

https://softeer.ai/practice/11002

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

해결방법

해당 문제에서 중요한 부분은 2가지이다. 첫번째는 CPTI 지표 비교하는 방법, 두번째는 리스트 순회 방법을 고려해야한다. 

CPTI 비교하는방법

CPTI는 2진법의 문자열로 입력된다. 2자리 이하로 지표가 다른 경우를 찾는것이므로 XOR연산과 비트 카운트를 통해 쉽게 해결이 가능하다.

리스트 순회

문제에서 주어진 조건에 따르면 O(NlogN)의 시간복잡도까지 가능하다. 그러므로 모든 경우를 조회하기 위해 N번씩 2중 반복문으로 해결할 수 없다. 그러므로 2중 반복문에서 반복 횟수를 줄이는 로직이 필요하다. 내가 해결한 방법은, 0..N까지의 이중 반복문을 사용했을때 같은 경우를 2번씩 검토하기때문에 해당 과정을 해결할 수 있도록 inner loop에서 반복자를 outer loop의 반복자 + 1부터 시작하도록 하였다.

해당 방법이 가능한 이유는, outer loop의 반복자는 이미 검토한 값이며 앞뒤 순서가 상관없는 조합만 검토하면 되는 문제이기 때문이다. 이 방법으로 개선한 결과 O(N^2)이지만, 실질적인 연산 횟수는 N(N-1) / 2으로 제한시간안에 문제를 해결할 수 있다.

 

소스코드

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

public class Main {
    static int M, N;
    static int[] personalities;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        N = Integer.parseInt(line[0]);
        M = Integer.parseInt(line[1]);
        personalities = new int[N];

        for(int i = 0; i < N; i++){
            personalities[i] = Integer.parseInt(br.readLine(), 2);
        }

        int answer = 0;
        for(int i = 0; i < N; i++){
            for(int j = i + 1; j< N; j++){

                int cnt = Integer.bitCount(personalities[i] ^ personalities[j]);

                if(cnt <= 2)
                    answer++;
            }
        }

        System.out.println(answer);
        
    }
}