[백준] 2830 : 행성 X3

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

2830번: 행성 X3

 

위 문제는 비트마스킹 문제이다.

XOR한 값들을 서로 더하면 된다고 생각할 수 있지만, n의 범위로 인해 O(N^2)으로 시간초과가 발생한다.

 

시간초과가 발생한 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int answer = 0;
        int[] resident = new int[n];
        for (int i = 0; i < n; i++) {
            resident[i] = Integer.parseInt(bf.readLine());
        }
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                answer += resident[i] ^ resident[j];
            }
        }
        System.out.println(answer);
    }
}

O(N^2) => 시간 초과!  ㅠㅠ

 

XOR 값 구하기

시간초과가 나지 않도록 XOR 값을 구하는 방식을 변경하자.

 

문제에서는 총 n명이 주어질 때, 2명씩 짝지어 친밀도(XOR)를 구한 값의 총 합을 구해야한다.

XOR값은 0과 1이 만났을때 비트 위치를 반영하여 값이 구해진다.

 

예시

1과 0이 만났을때 XOR 값이 생성될 수 있는 조건이 되고, 5번째 자리수이므로 16이 더해진다.

마찬가지로 XOR값을 구하면 총 XOR 값은 16 + 8 + 1 = 25이 된다.

 

해결 방법

1. 각 비트마다 1의 개수를 구해 배열에 저장한다.

2. 각 자리수마다(비트 마다) XOR 값이 생성되는 경우의 수에 비트 위치를 곱해 값을 구한다.

  XOR 값 = (0의 개수 * 1의 개수 ) * 비트 위치 값

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 1. 입력받기
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());

        // 2. 1의 개수 저장하기
        long answer = 0;
        int[] countOneBits = new int[20]; // 1,000,000의 이진 표현은 최대 20비트 필요
        for (int i = 0; i < n; i++) {
            int resident = Integer.parseInt(bf.readLine());
            for (int j = 0; j < 20; j++) { // 자리수마다
                if ((resident & (1 << j)) != 0) { // 1이 존재하면 +1
                    countOneBits[j]++;
                }
            }
        }
        // 3. 친밀도 구하기
        // XOR 값 = 0의 개수 * 1의 개수 * 비트 값
        for (int i = 0; i < 20; i++) { // 자리 수 마다 친밀도 구하기
            long zeroCount = n - countOneBits[i]; // 0의 개수
            long oneCount = countOneBits[i]; // 1의 개수
            answer += zeroCount * oneCount * (1 << i); // 비트 위치 반영하여 값 구함
        }
        // 4. 정답 출력하기
        System.out.println(answer);
    }
}

 

 

c++에서 java로 언어를 바꾼 이후로 알고리즘 실력이 x-3배 된 것 같다.

하지만 알고리즘 기본 바탕 실력은 있으니 빠르게 체화해서 풀 수 있도록 노력해야겠다!