행성 X3 - 백준 2830번

https://www.acmicpc.net/problem/2830

import java.util.Scanner;

public class Main {
    public static int X3Person (int a, int b) {
        return a ^ b;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] X3 = new int[N];

        for (int i = 0; i < N; i++) {
            X3[i] = sc.nextInt();
        }
        int result = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                result += X3Person(X3[i], X3[j]);
            }
        }
        System.out.println(result);
    }
}

for 문으로 행성 주민들의 이름을 얻고, XOR 연산자로 값을 구하려고 하니 시간초과로 실패..

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        sc.nextLine();
        int[] oneCnt = new int[20];
        for (int i = 0; i < N; i++) {
            int X3Person = Integer.parseInt(sc.nextLine());
            for (int j = 0; j < 20; j++) {
                if ((X3Person & (1 << j)) > 0) {
                    oneCnt[j]++;
                }
            }
        }
        long result = 0;
        for (int i = 0; i < 20; i++) {
            int zeroCnt = N - oneCnt[i];
            result +=(1L << i) * zeroCnt * oneCnt[i];
        }
        System.out.println(result);
    }
}

문제풀이

접근방식

N 은 사람의 수를 의미

1. 각 비트 위치에서 1의 갯수를 세기 위한 배열 초기화

int[] oneCnt = new int[20]

-최대 20비트까지 고려하기 위해 배열 초기화

2. 입력받은 숫자의 각 비트 위치에서 1의 갯수를 셈

for (int i = 0; i < N; i++) {
    int X3Person = Integer.parseInt(sc.nextLine());
    for (int j = 0; j < 20; j++) {
        if ((X3Person & (1 << j)) > 0) {
            oneCnt[j]++;
        }
    }
}

-X3Person 은 각 사람의 숫자를 의미
-1 << j 는 비트 시프트 연산으로, j 번째 비트 위치에 1을 두는 역할을 함
-X3Person & (1 << j) 는 X3Person 의 j번째 비트가 1인지 확인하는 연산. 결과가 0보다 크면 해당 비트가 1이라는 뜻
-각 비트 위치에서 1의 갯수를 배열 oneCnt에 저장

3. XOR 계산을 위한 조합 수 계산

long result = 0;
    for (int i = 0; i < 20; i++) {
        int zeroCnt = N - oneCnt[i];
        result +=(1L << i) * zeroCnt * oneCnt[i];
    }
    System.out.println(result);
}

-zeroCnt는 각 비트 위치에서 0의 갯수를 의미
-1L << i 는 i번째 비트 위치에 1을 두는 연산
-각 비트 위치에서 1이 되는 조합의 수를 계산하여 결과에 더함