2830 행성 X3 - 골드3

문제 출처 : https://www.acmicpc.net/problem/2830

정답 참고 : https://velog.io/@wellsbabo/%ED%96%89%EC%84%B1-X3%EB%B0%B1%EC%A4%802830%EB%B2%88

1. 문제

상근이는 초등학교 졸업 여행으로 외계 행성 X3에 방문했었다. 이 행성에 사는 사람들의 이름은 모두 자연수이다. 행성의 거주민은 모두 서로를 알고 있다. 두 X3인은 그들의 친밀도를 자신의 이름을 이진수로 바꾸어서 계산한다. 두 이름을 이진수로 바꾸고, 자리수가 짧은 쪽을 기준으로 정렬한다. 이때, 두 이진수의 각 자리 아래에 두 자리가 같으면 0을, 다르면 1을 적는다. 이 결과 이진수를 다시 10진수로 바꾸면 그들의 친밀도가 된다.

예를 들어, 10과 19의 친밀도는 25이다.

1 0 0 1 1 = 19
0 1 0 1 0 = 10
--------------
1 1 0 0 1 = 25

행성의 가치는 이 섬에 있는 모든 친밀도의 합이다. 행성 거주민들의 이름이 주어졌을 때, 행성의 가치를 구하는 프로그램을 작성하시오.

입력 첫째 줄에 X3 거주민의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 다음 N개의 줄에는 거주민의 이름이 주어진다. 이름은 1,000,000보다 작거나 같은 자연수이다.

출력 첫째 줄에 행성 X3의 가치를 출력한다.

예제1

2
19
10

=> 25

예제2

3
7
3
5

=> 12

2. 정답 소스코드

import java.io.*;

public class Main {
    static int MAX_BIT = 20;
    
    public static void main(String[] args) throws IOException {
        long result = 0;
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        long[] bit = new long[MAX_BIT];
        for (int i = 0 ; i < n ; i++) {
            int num = Integer.parseInt(bf.readLine());
            int idx = 0; //자리수를 표시
            //이진수로 변화하며 각 자리수 배열에 합
            while (num != 0) {
                int tmp = num % 2;
                num /= 2;
                if (tmp == 1) {
                    bit[idx]++;
                }
                idx++;
            }
        }

        for (int i = 0 ; i < MAX_BIT ; i++) {
            result += (long)Math.pow(2,i) * bit[i] * (n-bit[i]);
        }

        System.out.println(result);

    }
}

3. 풀이 방법

예) 7, 5, 3에 대한 친밀도를 구하고 싶을 경우

1) 숫자 7,5,3은 아래와 같이 이진수로 변경된다

7 => 0 1 1 1
5 => 0 1 0 1
3 => 0 0 1 1 
(왼쪽에서 오른쪽으로 2^3, 2^2, 2^1, 2^0)

2) 숫자 7,5,3의 각 2^0 ~ 2^3자리까지 수를 살펴보면 1과 0의 등장 빈도는 아래와 같다

  2^3 2^2 2^1 2^0
  ---------------
7 |0   1   1   1
5 |0   1   0   1
3 |0   0   1   1 

3) 이 때, 각 자리수별로 나올 수 있는 XOR연산 결과의 모든 경우 중 결과값이 1인 갯수를 구한다

2^0 => 1 1 1 => (11, 11, 11) => (0개)
2^1 => 1 0 1 => (11, 10, 01) => (10, 01) (2개)
2^2 => 1 1 0 => (11, 10, 01) => (10, 01) (2개)
2^3 => 0 0 0 => (00, 00, 00) => (0개)

4) 각 값들은, “1의 갯수 x 0의 갯수” 값과 같다

2^0 => 1 1 1 => 3(1의 갯수) x 0(0의 갯수) = 0
2^1 => 1 0 1 => 2(1의 갯수) x 1(0의 갯수) = 2
2^2 => 1 1 0 => 2(1의 갯수) x 1(0의 갯수) = 2
2^3 => 0 0 0 => 0(1의 갯수) x 3(0의 갯수) = 0

5) 최종적으로, “1의 갯수 x 0의 갯수 x 2^n” 값과 같다

2^0 => 1 1 1 => 3 x 0 x 2^0 = 0
2^1 => 1 0 1 => 2 x 1 x 2^1 = 4
2^2 => 1 1 0 => 2 x 1 x 2^2 = 8
2^3 => 0 0 0 => 0 x 3 x 2^3 = 0

합계 : 12