[백준 2830번][Java][비트연산자] 행성 X3

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

풀이

• n의 범위가 1,000,000이기 때문에 이중for문을 사용하면 시간복잡도가 O(n^2)이 되어 시간초과가 된다.

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

public class Practice {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] names = new int[n];

        for (int i = 0; i < n; i++) {
            names[i] = Integer.parseInt(br.readLine());
        }

        int total = 0; // 행성 가치의 총합

        // 친밀도 계산
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int num1 = names[i], num2 = names[j];
                int bit = 1;
                int intimacy = 0; // 친밀도

                // 두 수를 2진수로 변환하며 친밀도 계산
                while (num1 > 0 || num2 > 0) {
                    if (num1 % 2 != num2 % 2) {
                        intimacy += bit;
                    }

                    bit *= 2;
                    num1 /= 2;
                    num2 /= 2;
                }
                total += intimacy;
            }
        }
        System.out.println(total);
    }
}

비트 연산자 풀이

• 검색을 통해 1의 개수 0의 개수 2^(자리수-1) 을 더하면 행성의 가치를 구할 수 있다는 풀이를 얻었다.
• 1,000,000는 2^20이므로 크기가 20인 자릿수당 1의 개수를 저장할 배열 선언

/*
    비트연산자 - 백준 2830번
 */

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 n = Integer.parseInt(br.readLine());
        int[] names = new int[n];
        int[] count = new int[20];
        long sum = 0;

        // 모든 주민 이름 담기
        for (int i = 0; i < n; i++) {
            names[i] = Integer.parseInt(br.readLine());
        }

        // 각 자리수의 1의 개수 세기
        for (int i = 0; i < n; i++) {
            int name = names[i];
            int index = 0;
            while (name > 0) {
                count[index++] += name % 2; // count[0]부터 index를 1씩 증가시키며 비트가 1인 경우 1씩 저장
                name /= 2; // 비트에 저장한 값 만큼 뺀 것과 동일
            }
        }

        // 행성 가치 구하기
        for (int i = 19; i >= 0; i--) {
            sum += (long) count[i] * (n - count[i]); // 비트가 1인 경우 * 비트가 0인 경우
            sum <<= 1; // sum에 2를 곱한 것과 같은 효과
        }
        sum >>= 1; // 마지막은 2를 안 곱해도 괜찮은데 for문의 마지막에 곱했으므로 2로 나누기
        System.out.println(sum);
    }
}

• 비트연산자가 헷갈려서 손으로 계산해 가며 확인했다.
  

  

• 다음에는 스스로 비트연산자 이용하여 풀기!