[Algorithm] Softeer_CPTI (JAVA)

📝문제

https://softeer.ai/practice/11002

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

---

💡풀이

문제 유형

비트마스킹

브루트포스

 

걸린 시간

30분

 

시간 복잡도

O(N^2)

 

풀이 방법 도출

java의 비트연산을 모르면 풀기 어려운 문제다.

이 문제에 필요한 개념만 정리하면 다음과 같다.

 

XOR 연산(^) => 두 수의 각 자리수가 다른 경우 1로 변환한다.

Integer.bitCount 메서드 => 이진수에서 1의 개수를 세어주는 함수이다.

 

Integer.parseInt(br.readLine(), 2); => 2진수로 표현된 문자열을 10진수 정수로 변환한다.

 

입력받은 이진수의 모든 쌍을 검사해 각 자리수가 다른 경우가 2 이하인 경우를 세어주었다.

 

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[] binary = new int[N];
        //성격이 두가지만 다르면 친밀감을 느낌
        for(int i = 0; i < N; i++){
            binary[i] = Integer.parseInt(br.readLine(), 2);
        }

        int count = 0;
        for(int i = 0; i < N; i++){
            for(int j = i+1; j < N; j++){
                int diff = Integer.bitCount(binary[i]^binary[j]);
                if(diff <= 2){
                    count++;
                }
            }
        }

        System.out.println(count);
    }
}

---

🤔Review

XOR 연산(^),  Integer.bitCount 잘 알아갑니다..~