백준 2830 행성 X3

첫 시도) 시간 초과 

public class Main {
    public static void scorecalculator(int[] people){
        int score = 0;
        for(int i=0; i<people.length-1; i++){
            for(int j=i+1; j<people.length; j++){
                score+=people[i]^people[j];
            }
        }

        System.out.println(score);
    }
    public static void main(String[] args) {
        int N;
        Scanner sc = new Scanner(System.in);

        N= sc.nextInt();

        int[] people = new int[N];
        for(int i=0; i<N; i++){
            people[i]=sc.nextInt();
        }

        scorecalculator(people);
    }
}

 

시간 초과가 뜨길래 Scanner를 사용해서 그런가보다 싶어 BufferedReader로 다시 수정해 보았다.

 

두번째 시도) 시간 초과

public class Main {
    public static void scorecalculator(int[] people){
        int score = 0;
        for(int i=0; i<people.length-1; i++){
            for(int j=i+1; j<people.length; j++){
                score+=people[i]^people[j];
            }
        }

        System.out.println(score);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] people = new int[N];

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

        scorecalculator(people);
    }
}

여전히 시간초과가 발생했고, 시간복잡도가 O(n^2)인 것이 문제였다.

 

세번째 시도)

XOR 연산은 두 비트가 서로 다를 때만 1의 결과를 반환한다. 따라서 각 비트 위치에서 1과 0이 얼마나 만나는지에 주목해야한다.

각 비트의 1과 0의 개수를 계산하고 해당 개수를 곱해주면 해당 비트 위치에서 가능한 모든 XOR 결과 합을 구할 수 있다.

public class Main {
    public static void scorecalculator(int[] people){
        long score = 0; //int score = 0;  => 오답!
        int n = people.length;

        for(int bit = 0; bit<31; bit++) {//각 비트마다
            long countOne = 0;

            for(int person : people){
                if((person & (1<<bit)) != 0){
                    countOne++; // 1인 비트 개수 세기
                }
            }
            long countZero = n-countOne;
            score += (1L << bit) * countOne * countZero;
        }

        System.out.println(score);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] people = new int[N];

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

        scorecalculator(people);
    }
}

 

핵심 로직에 사용된 기본 개념

비트 AND 연산자 & : 두 정수의 이진 표현 비교 시, 각 비트 위치에서 모두 1인 경우에만 해당 위치의 결과가 1이 된다.

ex) 1010(2) & 1100(2) = 1000(2)

 

비트 AND 연산은 특정 비트들이 1인지 확인하고 싶은 상황에 유용하게 사용될 수 있다. 해당 비트 위치에서 1이 있는 마스크를 만들고 & 연산을 수행하면 된다.

ex) 정수 'n'에서 3번째 비트(2^2의 위치)가 1인지 n & (1<<2)의 연산을 통해 확인할 수 있다. 결과가 1이라면 해당 비트는 1이 된다.

 

(num <<bit) bit만큼 num을 레프트 쉬프트 연산 

1 << 0 = 1

1 << 1 = 10(2)

1 << 2 = 100(2)

...

1 << n = 2^(n-1)

 

 

그런데 이번에도 틀렸다는 결과를 받았고, 원인은 int score = 0;에 있었다. 정수 오버플로우 문제였고, int만 long으로 바꾸어주었더니 해결되었다.

 

정수 오버플로우 : 'int' 타입은 32비트 정수를 저장하고, 최대값은 약 2.1억(2^31 -1)이다. 계산 결과가 'int'의 최대값을 초과하면, 오버플로우 문제가 발생하여 예상치 못한 음수 값이 나올 수 있다.

 

문제의 입력 크기와 결과 : 문제에서 거주민의 수 'N'이 최대 1,000,000이고, 각 이름도 최대 1,000,000이라고 하였다. 모든 가능한 쌍의 친밀도를 더한다면 'int'범위를 초과할 가능성이 있다. 예를들어, 모든 거주민의 이름이 1,000,000이고, 거주민의 수가 1,000,000이라면, 최종합은 매우 큰 수가 될것이다.

 

'long'의 사용 : 'long'은 64비트 정수를 저장하며, 최대값은 약 9.2경(2^63-1)이다. 따라서 'long'을 사용하면 훨씬 더 큰수들도 안전하게 처리할 수 있어 오버플로우를 방지할 수 있다.