[백준] #2830 행성 X3

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

2830번: 행성 X3

 

---

문제 이해하기

거주민의 이름은 10진수이며, 친밀도 연산을 위해서는 이진수로 바꿔야한다.

친밀도 연산은 각 자리수가 같다면 0, 다르다면 1로 연산을 수행하고,

주민 별로 2진수 연산 값을 모두 더해 10진수로 변환하면 행성의 전체 친밀도가 나온다

따라서 내가 생각한 문제의 포인트는 아래와 같았다.

1. 10진수를 2진수로 변환하기
2. 2진수로 변환한 값을 가장 긴 자리 수에 맞춰서 바꾸기
3. XOR 연산

( 글 하단에 시행착오가 담겨있으니 잘 이해가 되지 않는다면 해당 부분을 먼저 읽고 읽어도 좋을 것 같다 )

 

문제 해체하기

1. 2진수 변환

친밀도 연산을 위해선 2진수로 변환해야 하는데, 2로 나눈 나머지 값을 int [ ] 배열에 차례대로 넣어준다.

이렇게 넣어주면 굳이 값을 가장 긴 길이에 맞춰 shift 하지 않아도 된다.

 

배열의 크기는 문제에서 제시한 “이름은 1,000,000보다 작거나 같은 자연수” 에 따라 다음과 같이 계산해보면 된다.

따라서 가장 긴 이진수 이름이 20자리를 넘지 않기 때문에 int[20] 으로 생성해주면 된다.

 

 

2. 친밀도 연산

각 이름 별로 XOR 연산을 수행해야 한다면, 이중 for문으로 인해 O(n^2) 의 시간 복잡도가 발생할 수 있다.

따라서 XOR 연산이 아닌, 그 안의 규칙을 찾아서 연산해주어야 한다.

(실은 해당 부분에서 규칙을 찾는 것이 가장 어려워 다른 블로그를 참고하였을 때 각 자리 수의 0의 개수와 1의 개수, 그리고 각 자리수의 가중치를 곱해주면 된다고 하였지만 명확히 이해가 되지 않아 다음과 같이 정리해보았다)

 

이렇게만 보았을 땐, 어떤 규칙이 있는지 쉽게 떠오르지 않는다.

그래서 다시 뜯어보면

XOR 연산은 결국, 0과 1이 조합이 되어야만 1을 나타내기 때문에

0의 개수와 1의 개수를 구해서, 두 숫자의 조합 가능 개수를 알면 되는 것이였다.

(상의 2벌, 하의 1벌이라면 총 2개의 착장을 입을 수 있다… 뭐 이런 개념이였던 것이다..)

 

따라서 해당 문제를 풀기 위해 아래와 같은 Point를 고려하여 풀었다.

 

코드

BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());

int MAX_SIZE = 20; // 이름의 길이는 최대 20
int[] name = new int[MAX_SIZE];

 

X3 행성 거주민 수 n을 받아온다.

이름의 최대 길이는 1,000,000 보다 작거나 같은 자연수라고 조건이 주어졌기 때문에 최대 20으로 설정해

배열을 생성한다

 

for(int i=0; i<n; i++) {
    int decimal = Integer.parseInt(br.readLine()); // 주민의 십진수 이름
    int index = 0;
    // 2진수로 변환, 나머지 값들을 차례대로 배열에 넣어줌
    while(decimal > 0){
        name[index] += decimal % 2;
        decimal /= 2;
        index++;
    }
}

 

10진수 이름(decimal)을 받아온다

이후 while문으로 decimal 값이 0과 같거나 작을 때까지 2로 나누면서 2진수로 변환하는데

이때 나머지 값들을 name[] 에 차례대로 넣어준다.

 

for 문을 거주민 수 만큼 반복하며 name[] 에 값을 계속 더해준다.

이름을 모두 name[]에 더했을 때,

name[i] 값은 1의 개수이고 (; 1과 0이 n번 더해진 값이기 때문에 1의 개수와 동일함)

, 0의 개수는 n(이름개수) - name[i](1의개수) 이다.

 

 

🚨 오류발생

long answer = 0;
for(int i=0; i<MAX_SIZE; i++){
    int zeroNum = n - name[i];
    //          0의 개수 * 1의 개수 * 2의 제곱수
    answer += zeroNum * name[i] * (long) Math.pow(2, i);
}

System.out.print(answer);

 

IDE 상에서는 오류가 없었는데, 백준에서는 틀렸다는 결과가 나왔다.

어떤 부분이 문제인가 봤는데, 아마 Long 타입으로 선언된 answer에 int로 된 zeroNum 연산이 더해져서

겉으로 보이기엔 문제가 없지만, 내부에서는 값이 다르다고 판단이 된 것 같다.

(만일 다른 이유라면 의견 남겨주세요..😥)

 

💡 수정된 코드

// 1의 개수 = name[i] 값
// 0의 개수 = n - name[i] 값
// 정답의 길이가 int 형보다 길 수 있기 때문에 long 타입으로 선언
long answer = 0L;
// 이름 배열을 돌면서, 각 자리수의 1과 0의 개수를 구해 해당 가중치만큼 곱해준다
for(int i=0; i<MAX_SIZE; i++){
    //          0의 개수 * 1의 개수 * 2의 제곱수
    answer +=  (long) Math.pow(2, i) * (n - name[i]) * name[i];
}
System.out.print(answer);

 

위에서 정리했듯이 1의 개수는 name[i] , 0의 개수는 n-name[i] 이고,

Java에서는 제곱수를 계산하는 연산이 없기 때문에 `Math.pow(밑수, 지수)` 를 사용하면 된다.

(다른 예제에서는 (1L << i) 를 사용하였는데, 해당 내용은 나중에 이해하고 정리해보도록 하자)

 

전체 코드

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 MAX_SIZE = 20; // 이름의 길이는 최대 20

        int[] name = new int[MAX_SIZE];
        for(int i=0; i<n; i++) {
            int decimal = Integer.parseInt(br.readLine()); // 주민의 십진수 이름
            for(int j=0; j<MAX_SIZE; j++){
                if((decimal & (1<<j)) > 0)
                    name[j]++;
            }
        }

        long answer = 0;
        for(int i=0; i<MAX_SIZE; i++){
            answer += (long) Math.pow(2,i) * (n-name[i]) * name[i];
        }

        System.out.print(answer);
    }
}

 

내가 생각한 방법 (오류)

1. 10진수를 2진수로 변환하기

우선 JAVA 에서 10진수를 2진수로 바꾸는 방법 두 가지를 생각했다

1. Integer.toBinaryString( );
2. 10진수를 2로 나눈 나머지 값들의 정렬

 

2. 2진수로 변환한 값을 가장 긴 자리 수에 맞춰서 바꾸기

1번 과정에서 2진수로 잘 변환을 마쳤다면,

친밀도 연산을 위해선 각 주민들 이름의 길이를 맞추기 위해, 가장 긴 길이에 맞춰 이름 앞에 0을 추가해주어야 했다.

하지만 여기서 발생한 고민이 다음과 같았다.

1. 주민 이름을 int 형으로 관리한다면, 앞에 0을 추가하는 것 자체가 불가능
2. 배열로 관리할 경우 추가해야 하는 0의 개수만큼 값을 뒤로 미뤄야하기 때문에 경우에 따라 for문 연산 횟수가 지나치게 많아질 수 있음
3. toBinaryString( ) 을 통해 2진수로 바꾸더라도, 값의 앞에 0을 넣기 위해선 for문 연산이 필요 → 2번과 같이 지나치게 많아질 수 있음
4. shift 연산?

 

3. XOR 연산

만일 자리수를 잘 맞췄다고 하더라도, 주민의 최대 수는 1,000,000 명이기 때문에

최악의 경우 시간 복잡도가 O(n^2) 이 되어 시간 초과가 발생할 수 있다.

 

느낀점

문제를 명확하게 이해하는데만 반나절이 넘게 걸린 것 같다,,

비교적 간단한 비트연산이라고 생각했지만, 시간복잡도를 고려해 단순 연산이 아닌 규칙을 찾아내는 것이 가장 어려웠다.

다른 블로그들을 봐도 '각 자리수의 1과 0의 개수를 구해 곱하면 된다!' 만 나와있지, 왜 그게 규칙인지는 설명이 없어서 이해해보기 위해 한참 씨름을 했는데, 막상 이해하고 보니 왜 안썼는지도 알 것 같기도,,,

그치만 나같은 사람들을 위해서 내가 고민해본 흔적을 남겨본다.

 

참고자료

https://blog.naver.com/jhsfully/223078021804

2830번: 행성 X3