백준2830번) 행성 X3

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

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

◇ 입력

첫째 줄에 X3 거주민의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 다음 N개의 줄에는 거주민의 이름이 주어진다. 이름은 1,000,000보다 작거나 같은 자연수이다.

◇ 출력

첫째 줄에 행성 X3의 가치를 출력한다.

---

◆ 풀이

XOR 연산을 하라는 의미다.

x ^ y 한 값을 모두 구한 뒤 더한 값을 2분의 1 하면 금방 구할 수 있을 것이다.

하지만 다른 말로 하면 먼저 계산한 i보다 j가 큰 경우에만 연산을 하면 된다는 의미이다.

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[] input = new int[n];
        for(int i=0; i<n; i++){
            input[i] = Integer.parseInt(br.readLine());
        }

        int result = 0;
        for(int i = 0; i<n; i++){
            for(int j = n-1; j>i; j--){
                result += input[i] ^input[j];
            }
        }
        System.out.println(result);
    }
}

아마 N이 1백만이어서 생긴 문제같다.

생각해보면 경우의 수가 N*(N-1)/2 개이기 때문에 시간초과가 나올 수 있다.

현재 나의 코드는 시간 복잡도가 O(N^2)이다.

시간 제한은 1초. 최소 O(N)으로 줄여야 가능할 것으로 보인다.

어떻게 하면 시간 복잡도를 줄일 수 있을까?

좀 오래 고민해보았지만 딱히 떠오르는 수가 없어 힌트를 얻고자 검색해보았다.

그랬더니 동일한 수의 개수를 센 뒤 해당 자리의 수를 곱한 값을 누적시키면 된다고 되어있다.

그래서 코드를 다시 작성해보았다.

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());
        
        // 1백만은 2의 20승보다 작기 때문
        int[] input = new int[20];
        final int checkBit = 0b1;
        for(int i=0; i<n; i++){
            int value = Integer.parseInt(br.readLine());
            int index = 0;
            while(value>0){
                input[index++]+=value&checkBit;
                value>>=1;
            }
        }

        final long val = 1L;
        long result = 0;
        for(int i = 0, iMax = input.length; i<iMax; i++){
            int cnt = input[i];
            if(cnt==0)
                continue;

            result+=(val<<i)* cnt * (n-cnt);
        }
        System.out.println(result);
    }
}

쉽지 않았다.