[백준 골드3] 2830번 행성 X3 / Java

백준

---

행성 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진수로 변환해야해서 Integer의 내부 메서드인 toBinaryString()를 통해서 하려고했는데, 생각해보니까 그렇게 하면 인덱스 방향이 반대로 될 것같아서 하지 않았다.

 

N개의 Integer들이 들어오기때문에, 모든 Integer 변수들을 2진수로 변환하면서 배열이 0으로 초기화 되어있는 정수형 배열을 하나 만들고, 0번 인덱스의 1의 갯수를 구한다.

 

문제의 규칙상 특정 인덱스의 1의 갯수 * (N - 특정 인덱스의 1의 갯수)를 하게 되면 가치를 구할 수 있다(+ 추가로 2^(N-1)를 해줘야 구할 수 있다고한다. 그래서 마지막에 반복문에서는 sum<<1, 나와서는 sum >> 1를 하는 것을 볼 수 있다)

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

class Main{
    public static void main(String[] args)
            throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> nums = new ArrayList<>();

        for (int i = 0; i <N ; i++) {
            nums.add(Integer.parseInt(br.readLine()));
        }
        // [19,10...]
        int[] count = new int[20];
        for(Integer num: nums){
            int idx = 0;
            while(num > 0){
                count[idx++] += num % 2;
                num /= 2;
            }
        }
        long sum = 0L;
        for (int i = 19; i >= 0; i--) {
            sum += (long)count[i] * (N - count[i]);
            sum <<= 1;
        }
        sum >>= 1;
        System.out.println(sum);

    }
}

---

결과

성능 요약

메모리: 266272 KB, 시간: 624 ms

---

후기

아직 비트 연산자에 익숙하지 않아서, 문제를 검색해보고 풀엇던 것같다.

또한, 문제를 구현만 하려다보니, 쉬운 알고리즘조차 생각하지 못하고 돌아갔던것 같다.