(백준/자바) 힌트문제1 04. 비트연산자 - 백준 2830번 문제 : 행성 X3

2830번: 행성 X3 (acmicpc.net)

2830번: 행성 X3

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

public class Bit_04 {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        ArrayList []arr = new ArrayList[N];
        int total = 0;

        for (int i = 0; i < N; i++) {
            //toBinary
            arr[i] = toBinary(Integer.parseInt(br.readLine()));
        }
        for (int i = 0; i < N ; i++) {
            for (int j = i + 1; j < N ; j++) {
                ArrayList tmpResult = new ArrayList();
                int bigSize = arr[i].size() > arr[j].size() ? arr[i].size() : arr[j].size();
                while(arr[i].size() < bigSize){
                    arr[i].add(0,0);
                }
                while(arr[j].size() < bigSize){
                    arr[j].add(0,0);
                }
                for (int k = 0; k < bigSize; k++) {
                    if(arr[i].get(k) == arr[j].get(k)){
                        tmpResult.add(0,0);
                    }else{
                        tmpResult.add(0,1);
                    }
                }
                total += toDecimal(tmpResult);
            }
        }
        System.out.println(total);
    }
    public static ArrayList toBinary(int n){
        ArrayList list = new ArrayList();
        while(n != 1){
            list.add(0,n % 2);
            n /= 2;
        }
        list.add(0, n);
        return list;
    }
    public static int toDecimal(ArrayList list){
        int result = 0;
        for (int i = 0; i < list.size() ; i++) {
            result += (int)Math.pow(2,i) * (int)list.get(i) ;
        }
        return result;
    }
}

큰 어려움 없이 풀어봤는데 메모리 초과가 나온다.

 

 

풀이를 찾아보았다.

XOR 연산은 서로 다를 때 결과가 1 같을 때 0

모든 수들의 비트가 1인 갯수, 0인 갯수를 곱해주면 해당 비트의 총 경우의 수가 된다.

여기에 이진수 자릿수 만큼 곱해주면 손쉽게 구할 수 있다.

 * 총합은 long 자료형에 담아줘야된다. 왜냐면 행성민 이름 N이 1000000 이하의 자연수인데 1000000을 2진수로 바꾸면 20자리이기 때문에 int형으로는 불가

 

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

public class Bit_04 {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int oneArr[] = new int[21];
        String []arr = new String[N];
        long total = 0;

        for (int i = 0; i < N; i++) {
            //toBinary
            arr[i] = Integer.toBinaryString(Integer.parseInt(br.readLine()));
            for (int j = 0; j < arr[i].length(); j++) {
                char c = arr[i].charAt(arr[i].length() - 1 - j);
                if ( c == '1'){
                    oneArr[j] ++;
                }
            }
        }
        System.out.println(Integer.toBinaryString(1000000));
        for (int i = 0; i < oneArr.length; i++) {
            total += (long) oneArr[i] * ( arr.length - oneArr[i] ) * (int)Math.pow(2,i);
        }
        System.out.print(total);
    }
}