[Gold III] 백준 - 2830. 행성 X3 : Java

2830번: 행성 X3

 

 

 

이해하기

• 사람들의 이름은 모두 자연수
• 친밀도 = 이름을 이진수로 바꾸어 XOR 연산
• 행성의 가치 = 이 섬에 있는 모든 친밀도의 합

여기까지만 생각했을 때는, '사람들의 이름을 배열로 받아와서 for문을 이용하여 모두의 친밀도를 계산한 후 총합을 리턴해야겠다!'라고 생각했다. 그치만 그 방법으로는 절대 안 풀리더라...😢

 

문제에 나와있듯 1 <= N <= 1,000,000 인데, N이 1,000,000인 경우 엄청나게 많은 연산을 해야하고 그렇기에 시간 초과가 떴던 것이다.

 

그래서 결국 다른 분들의 풀이를 참고하여 해결하였다.

 

각 비트마다 0과 1이 나오는 횟수를 알고 있다고 한다면, 각 비트의 개수로 0과 1의 조합을 만들어낼 수 있다.

 

이 말이 이해가 잘 되지 않았는데 직접 예시를 들어보니 납득이 갔다.

 

1010, 0101, 1100 세가지의 맨 끝자리를 조합하여 보자.

XOR 연산은 서로 다른 경우 1, 같은 경우 0이 된다.

1이 되려면 0과 1의 조합이어야 하고 위의 경우 2가지 조합이 나오게 된다.

 

이걸 다시 생각해보면 0의 개수 X 1의 개수 = 조합의 개수 (2 X 1 = 2) 라고 적을 수 있다.

이 부분을 이해하는데 있어 많은 고민이 필요했다...

 

 

문제에 나왔던 예시로도 이렇게 풀어볼 수 있다. (맨 오른쪽 비트를 1의 자리라고 본 것이다.)

 

 

문제 풀이

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

public class no_2830 {
    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];  // 1 <= N <= 1,000,000 인데 2진법으로 하면 1,000,000은 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 idx = 0;
            while (name > 0) {
                count[idx++] += name % 2;   // count[0]부터 idx를 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);
    }
}

 

이 코드를 가지고 한 번 분석해보자.

 

int[] count = new int[20];

 

여기서 배열 사이즈를 20으로 잡은 이유는 거주민의 수 N이 1 <= N <= 1,000,000 이기 때문이다.

1,000,000 = 1000^2 인데, 2^9 < 1000 < 2 ^10 이기 때문에, 1,000,000 < 2^20 이 되게 된다.

 

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

 

names 배열에 주민 이름을 하나씩 넣는 코드이다.

 

for (int i = 0; i < N; i++) {
	int name = names[i];
	int idx = 0;
	while (name > 0) {
		count[idx++] += name % 2;
		name /= 2;
	}
}

 

이 부분이 제일 어렵게 느껴졌는데, 디버깅을 돌려보니 그리 어렵지 않은 코드였다.

names 배열을 돌면서 이름을 하나씩 가져와 name의 값으로 한다.

name이 0보다 크다면 while문을 계속 돌게 되는데, 한 번 돌 때마다 count[idx++] += name % 2를 하게 된다.

 

names = {7, 3, 5}일 때의 계산이다.

 

for (int i = 19; i >= 0; i--) {
	sum += (long) count[i] * (N - count[i]);
	sum <<= 1;
}
sum >>= 1;

 

count 배열을 돌며 비트가 0인 경우와 비트가 1인 경우를 곱하여 총합을 구하게 되는데, 간단해보이지만 이해가 잘 되지 않았다. 위의 계산에서 나온 count배열을 가지고 직접 해보았다.

 

 

예제의 출력과 같은 수가 나왔다!

 

 

마무리

이해는 됐지만, 다시 풀라고 하면 이런 규칙을 바로 찾아낼 수 있을까...?

수학적 풀이나 규칙 찾기가 제일 어렵게 느껴지는 것 같다.

 

여담이지만, 나는 2진수 문제를 풀 때, 가장 긴 길이를 구하고 그 길이에 맞춰 배열의 길이를 설정했다.

그런 후 숫자를 순서대로 집어넣고 싶었기 때문에, 그 길이보다 짧은 2진수는 '최대 길이 - 해당 2진수의 길이'만큼 0을 넣어주고, 그 다음부터 해당 2진수를 차례대로 넣었다.

말이 조금 횡설수설한데, 정리해보자면 아래와 같이 했다는 말이다.

 

순서대로 집어넣고 싶다는 강박이 있었던 것 같은데, 이렇게 되면 연산도 늘어나고 2진수 계산을 할 때도 복잡했다.

 

이 문제에 대해 고민하다 스터디원분의 정리글을 보았는데 머리를 한 대 맞은 것 같았다.

굳이 앞에서부터 넣을 필요가 없던 것이다!

 

뒤에서부터 차례대로 집어넣으면 최대 길이를 구하는 연산도, 길이 차만큼 0을 채워줘야 했던 것도, 뒤에서부터 2진수 연산을 해야했던 것도 전부 하지 않아도 된다는 것이었다.🥹

 

습관이 무섭다... 나는 모든 2진수 문제를 위와 같이 풀었었는데...!

 

 

 

참고

[백준] 골드III_2839: 행성 X3-Java

 

[백준] #2830 행성 X3

 

[백준 2830번] 행성X3 (자바)