행성 X3(백준2830번)

문제링크: https://www.acmicpc.net/problem/2830

나의 풀이

처음에는 모든 이름을 이진수로 바꾸어 XOR하면 되는 간단한 문제라고 생각했다. 하지만 그것이 아니라 각 2명씩 전부 XOR하고 그 결과값으로 나온 것을 총합하는 것이 문제의 내용이었다.

정말 문제 그대로 전체 이름을 XOR하고 그것을 더하는 것은 어림잡아 생각해도 O(N^2)를 넘어가는 시간 복잡도이기때문에 불가능했다.

그래서 고민하던 중 다른 글에서 힌트를 얻었다.

XOR 연산을 하기때문에
모든 수에 대해 (각 자리의 1의 개수) X (각 자리의 0의 개수)를 XOR 했을 때 각 자리의 1의 개수가 나오고, 그것을 전부 합한 뒤에 자리수를 곱해주면 된다.

예를 들어. 3개의 이진수 111, 110, 100 이라고 치면
3번째 자리수는 1이 3개, 0이 0개 -> 곱하면 0이 나온다. XOR은 서로 다른 수일때 1이 나오는데, 3번째 자리수는 세개의 수 모두 1이기 때문에 1의 개수가 0개가 맞다.
2번째 자리수는 1이 2개, 0이 1개 -> 곱해서 2개. 각 경우를 직접 해보면 [0,1], [0,1], [0,0]으로 1이 2개가 나오는게 맞다.
1번째 자리수는 1이 1개, 0이 2개 -> 곱해서 2개이다.
이렇게 각 자리수에서의 1의 개수를 찾은뒤
-> (0 2^2) + (2 2^1) + (2 * 2^0) = 6으로 이진수 110이 나온다.

소스코드

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        int[] one = new int[20];
        int num;
        int tmp = 0;
        int index;
        long answer = 0L;

        for(int i=0; i<n; i++){
            num = Integer.parseInt(sc.nextLine());
            index = 0; //자리수를 표시
            //이진수로 변화하며 각 자리수 배열에 합
            while(num != 0){
                tmp = num%2;
                num = num/2;
                if(tmp == 1){
                    one[index]++;
                }
                index++;
            }
        }

        for(int i=0; i<20; i++){
            answer += (1L<<i)*one[i]*(n-one[i]);
        }

        System.out.println(answer);
        
    }
}

후기

마지막 부분에 1L<<i는 다른 사람의 풀이를 참고하지 못했으면 생각을 못했을 것이다.
비트 연산을 알고는 있지만, 아직은 익숙하지 못한 상태이다.