(2830) 행성 X3

문제

문제
상근이는 초등학교 졸업 여행으로 외계 행성 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의 가치를 출력한다.

---

문제 풀이

비트연산자와 이진수에 대한 개념이 잘 잡혀 있어야 풀 수 있는 문제였다. 처음에는 단순히 2진법을 변환하고 단순히 0,1을 비교하여 만들면 되겠다고 생각하고 접근 했으나, 여러개가 입력이 되면서 해당 방식으로는 처리가 되지 않았음. 

 

결론적으로는 2진수 자릿수 마다 있는 1의 개수를 세고 나중에 연산을 해주는 방식으로 처리 하였음. 아래의 코드가 자릿수 마다 1이 몇 개가 존재하는지 체크하는 코드이다. 계산방식은 아래와 같다. 

    if ((v[j] & (1 << i)) != 0) {
        bcnt[i]++;
    }

 

i 는 0 부터 19 까지 증가가 되고 배열 v에는 외계인 이름이 들어 있다. 

 

이름이 9와 7인 외계인이 얼마나 친밀한지 예를들어 설명 하겠음.

 

정수 1을 이진법으로 변환하면 0001 그리고 정수 9를 이진법으로 변환하면 1001이다. 그리고 정수 9와 1을 and 연산자(둘 다 1일 때 1을 반환)로 계산을 하고 결과 값이 1이상일 경우 카운팅을 해주면 두 외계인이 이름에 있는1의 개수를 확인 할 수 있다. 아래는 i가 0을 때, 즉 쉬프트 연산자가 없을 때의 계산 결과이다. 

 

다음 반복문에서 i가 1이 되면 사진과 같이 1이 이동한다. 

 

그렇게 반복문을 돌고 나면 카운팅이 된 값을 배열로 담아 두면 아래와 같이 나온다. 

해당 배열의 인덱스를 2의 제곱승으로 사용을 하고 각 배열에 담겨 있는 값과 총 외계인 이름수 - 배열에 담겨 있는 값을 사용하여 계산을 한다. 

    for (int i = 0; i < 20; i++) {
        ans += (1L << i) * bcnt[i] * (n - bcnt[i]);
    }
    // 결과 값
    // 2^0 * 2 * 0 = 0
    // 2^1 * 1 * 1 = 2
    // 2^2 * 1 * 1 = 4
    // 2^3 * 1 * 1 = 8
    // ----------------
    // sum           14

---

나의 답안

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] v = new int[n];
        for (int i = 0; i < n; i++) {
            v[i] = sc.nextInt();
        }

        int[] bcnt = new int[20]; // 각 자리수별로 1이 몇 개 있는지

        for (int i = 0; i < 20; i++) {
            for (int j = 0; j < n; j++) {
                if ((v[j] & (1 << i)) != 0) {
                    bcnt[i]++;
                }
            }
        }

        long ans = 0;

        for (int i = 0; i < 20; i++) {
            ans += (1L << i) * bcnt[i] * (n - bcnt[i]);
        }

        System.out.println(ans);
    }
}