백준 2830번 : 행성 X3 [Java]

🎁 문제 링크

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

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

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

🎁 입출력 예시

🎁 코드

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int[] names = new int[num];
        long sum = 0L;
        
        // 모든 주민 이름 담기
        for (int i = 0; i < num; i++) {
            names[i] = Integer.parseInt(br.readLine());
        }
        //주어진 자연수의 최대값이 1,000,000이므로 2^10 (1024)은 decimal에서 대략적으로 0 세개를 나타낸다
        //이는 쉼표(,)를 기준으로 이해하면 정말 쉽다. 따라서 2^20이므로 배열의 크기는 20으로 하면 된다.
        int[] cnt = new int[20];

        for (int i = 0; i < num; i++) {
            int name = names[i];
            int index = 0;
            while (name > 0) {
                cnt[index++] += name % 2; // cnt[0]부터 index를 1씩 증가시키며 비트가 1인 경우 1씩 저장
                name /= 2; // 비트에 저장한 값 만큼 뺀 것과 동일
            }
        }
        
        for (int i = 0; i < 20; i++) {
            //비트 0인 경우 * 비트 1인 경우(zero * cnt[i])
            //(1L << i)는 위에서 설명한 비트 이동 연산자로 i가 증가함에 따라 2^i을 돌려받을 수 있다.
            int zero = num - cnt[i];   //비트가 0인 경우
            sum += (1L << i) * zero * cnt[i];
        }
        System.out.println(sum);
    }
}

🎁 코드 설명

1) BufferedReader를 통해 입력 값을 받는다

2) int[] cnt = 20개로 설정(주어진 자연수의 최대값이 1,000,000이므로 20개로 설정)

3) while문을 돌려서 cnt의 인덱스 값을 증가시키면서 %2 진행(비트가 1인 경우 1씩 저장)

4) 그리고 비트에 저장한 값 만큼 뺀 것과 동일하게 /= 2 진행

5) sum 값에 비트가 0인경우와 1인 경우를 곱셈 진행한다.

6) (1L << i)는 위에서 설명한 비트 이동 연산자로 i가 증가함에 따라 2^i을 돌려받을 수 있다.

7) 이렇게 하여 십의 자리로 재 변환하여 출력할 수 있다

🎁 참고 링크

https://gukin.tistory.com/14

시간복잡도, 큰수 다루기, 해법 설계 및 배운점들 - 백준 2830번: 행성 X3