백준 2830 문제 풀이

문제링크

찾아낸 규칙

주민의 모든 이름 조합을 구해서 xor한 결과를 모두 더하면 답이 나온다는 사실을 알았지만 이 알고리즘은 $O(n^2)$ 이라 시간 초과가 떴다.

모든 이름을 이진수로 바꾸고 각 자릿수 마다 1의 개수를 센다.
자릿수 별로 1의 개수 0의 개수 2의 자릿수만큼의 제곱을 모두 더해주면 답을 구할 수 있다.

코드 및 코드 설명

1000000 = $10^6$ = $(10^3)^2$ = $1000^2$ = $(2^{10})^2$ = $2^{20}$ 이므로
자리수 별 1의 개수를 세기 위해 int[] cntOne = new int[20]인 배열을 선언한다.

package pre;

import java.util.Scanner;

public class PlanetX3 {
    public static void solution(int[] arr){
        // 1. // 조합 모두 구해서 xor합 구하기 -> 시간 복잡도가 n^2이어서 시간초과 뜸
//        int sum = 0;
//        for(int i = 0; i<arr.length-1; i++){
//            for(int j = i+1; j<arr.length; j++){
//                sum+=(arr[i]^arr[j]);
//            }
//        }
//        System.out.println(sum);

        //2. 이진법의 1의 개수와 0의 개수를 곱하고 2의 자릿수 제곱을 통해 답 구하기
        // 최대 1000000이니까 2^20
        long[] cntOne = new long[20];
        for(int i = 0; i<arr.length; i++){ // 모든 주민의
            int name = arr[i];
            int j = 0;
            while(true){ // 이름을 이진법으로 바꾸고 각 자리의 1의 개수를 센다.
                if(name/2 == 0){
                    cntOne[j]++;
                    break;
                }
                cntOne[j++] += name%2;
                name/=2;
            }
        }
        long ans = 0;
        for(int i = 0; i<20; i++){
            ans += cntOne[i] * (arr.length-cntOne[i]) * (1<<i); //( 1의 개수) *( 0의 개수) * (2의 자리수만큼의 거듭제곱)
        }
        System.out.println(ans);


        //3. 이진법의 1의 개수와 0의 개수를 곱하고 2의 자릿수 제곱을 통해 답 구하기
        long[] cntOne2 = new long[20]; // 최대 1000000이니까 2^20
        for(int i = 0; i<arr.length; i++){ // 모든 주민의 이름을 순회하며 자릿수 별로 1의 개수를 센다.
            int name = arr[i];
            for(int j = 0; j<20; j++){
                if((name & (1<<j)) > 0) { // 1을 왼쪽으로 밀면서 자리별로 1의 유무를 구함
                    cntOne2[j]++; // 1이 있다면 자리수에 일의 개수를 1추가함.
                }
            }
        }
        long ans2 = 0;
        for(int i = 0; i<20; i++){
            ans2 += cntOne2[i] * (arr.length-cntOne2[i]) * (1<<i); //( 1의 개수) *( 0의 개수) * (2의 자리수만큼의 거듭제곱)
        }
        System.out.println(ans2);

    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] people = new int[n];
        for(int i= 0; i<n; i++){
            people[i] = sc.nextInt();
        }
        solution(people);
    }
}

시행착오 및 교훈

n의 제한이 1000000임을 확인하고 이건 $O(n^2)$으로 풀 수 없다는 걸 알았지만 모든 조합을 고려하는 $O(n^2)$ 알고리즘밖에 떠오르지 않았다. 검색하면서 찾아보니까 수학적으로 접근하면 다른 알고리즘으로 풀 수 있음을 알게 되었다! 이 문제를 경험삼아 다음에는 수학적으로 비트연산 문제를 풀어버려야지!