코딩 테스트 풀이 13 - 행성 X3

배효림·2023년 3월 20일

코딩테스트

목록 보기

13/20

✔ 문제

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

💡 접근 방법

두 이진수의 각 자리 아래에 두 자리가 같으면 0, 다르면 1 이라는 부분을 보고 XOR 연산이라는 것을 알았다. 그래서 처음에는 아래처럼 이중 포문으로 각 사람들의 친밀도를 ^ 연산을 통해 구했는데, 시간초과가 났다.

 for (int i = 0; i < numArray.length; ++i)
 {
        for (int j= i ; j < numArray.length ;++j)
        {
             answer += numArray[i] ^ numArray[j];
        } 
 }

그런데 굳이 사람들간에 XOR 을 하지 않아도, 사람들의 이름을 이진수로 바꾸었을 때 각 자리에 0과 1의 개수만 알 수 있다면 친밀도를 구할 수 있다. 친밀도가 오르는 건 0,0 이나 1,1 이 아닌 0,1 이나 1,0 이므로 해당 개수를 알 수 있다면 $2^{자리수}$ 에 0의 개수 * 1의 개수를 하면 된다. 예로들어서 TestCase 2 를 생각해보면,

3: 011
5: 101
7: 111

첫번째 자리수 ( $2^0$ ) 는 1이 3개, 0이 0개이다. 그럼 $2^0 \times 0 \times 3$ 이므로 0이 나온다. 1,1 이 0이므로 당연한 결과이다. 이어서 두번째 자리수는( $2^1$ ) 1이 2개 , 0이 1개이다. 그럼 $2^1 \times 2 \times 1$ 이므로 4가 나온다. (3과 5에서 1,0 5와 7에서 0,1이니까 1+1 = 2 거기에 자리수 생각하면 $2^1 \times 2$ 니까 같은 결과값이다) 비슷하게 세번째 자리수는 ( $2^2$ ) 1이 2개 0이 1개이므로 $2^2 \times 2 \times 1$ 이므로 8가 나온다. 전부 더하면 8+4 = 12이다.

그럼 문제를 풀기 위해서는 행성 사람들의 이름을 iterate 하며 자리수마다 전체 1의 개수와 0의 개수가 몇개인지를 구해야한다. 그 뒤에 위에서 한 것처럼 자리수에 1의 개수 * 0의 개수를 곱하면 된다 .

⭐ 코드

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 peopleNum = Integer.parseInt(br.readLine());

        int[] numArray = new int[peopleNum];
        long[] oneCount = new long[20];

        for (int i = 0; i < peopleNum; ++i)
        {
            numArray[i] = Integer.parseInt(br.readLine());

            for (int j = 0; j < 20; ++j)
            {
            	// 자리수마다 & 연산을 하면 그 자리에 1이 없다면 0 반환 (0 & 1 은 0 이므로)
                if (0 < (numArray[i] & (1 << j)))
                {
                    oneCount[j]++;
                }
            }
        }

        // 0의 개수 * 1의 개수
        long answer  = 0;
        for (int i = 0 ; i < 20 ; ++i)
        {
            answer += oneCount[i] * (numArray.length - oneCount[i]) * (1L << i);
        }

        System.out.println(answer);
    }
}

❔ 문제점

사실 위의 로직은 생각보다 빨리 구현했고 테스트 케이스 3가지도 문제가 없는데 제출만 하면 틀렸다고 나와서 어떤 것이 문제일까 한참 헤멨다. 다른 사람들 코드를 보고 두 가지를 수정하니 제출에서도 정답이라고 했다 :

long 으로 count array 를 만들고 answer 역시 long으로 할 것
count array를 처음에는 sort해서 max의 binary string 을 구해 해당 length로 맞추었는데 1,000,000 에 맞춰 20으로 바꾼 것.

사실 1,000,000 이 numArray[i] 의 제한선인데 왜 long으로 만들어야 제출 통과를 해야하는지 아직 잘 모르겠다. 2번 같은 경우에는 sort해서 max를 구하는 것보다 더 효율적인 방법 같다.

배효림

항상 위를 바라보는 프로그래머

이전 포스트

코딩 테스트 풀이 12 - 개수 세기

다음 포스트

코딩 테스트 풀이 13 - 행성 X3