백준 1322번: X와 K

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

 

주어진 자연수 X와 K에 대해서 X + Y = X | Y 를 만족하는 K번째 자연수 Y를 구하는 문제이다. 답이 2^31 +1 보다 클 수 있으므로 long을 사용해야 하며, 단순히 1부터 2^63 -1 까지 순회하여 탐색하면 시간 초과가 발생한다. 이를 시간 초과 발생 없이 푸는 방법은 비트마스크를 이용하는 것이다. X + Y = X | Y 를 만족한다는 것은 X와 Y가 겹치는 비트가 없다는 것이며, X의 비트를 제외하고 K번째 수를 찾으면 된다.

 

1부터 long 범위 까지 비트별 값을 오름차순으로 List에 넣은 후, 주어진 X의 비트마스크에 해당하는 비트를 List에서 제거하여 X를 제거한 비트들을 구한다. 예를들어, X=5이면, 2진수로 101이므로, List에서 첫번째, 세번째 숫자인 1, 4를 제거하게 된다. X가 4라면 2진수 100 이므로 세번째 숫자 4를 제거하게 된다.

List<Long> list = new ArrayList<>();
for (long i = 1L; i <= Long.MAX_VALUE / 2; i *= 2) {
    list.add(i);
}
List<Integer> bits = new ArrayList<>();
while (x > 0) {
    bits.add((int) (x % 2));
    x /= 2;
}
for (int i = bits.size() - 1; i >= 0; i--) {
    if (bits.get(i) == 1) {
        list.remove(i);
    }
}

 

K번째 수는 list의 수들을 2진수 비트라고 생각하고 K를 만든다고 생각하면 된다. 예를 들어, X = 5, K = 2 라고 한다면

list 는 2, 8 16 ....... 로 채워지게 되고, K는 2진수로 나타내면 10, 비트 자리의 오름차순으로 나타내면 01이 되므로 8이 되며 K=3 이라면 11이 되어 2+ 8 = 10 Y는 10이 된다. 마찬가지로 K=5 이면 101로 Y는 18이 된다.

bits.clear();
while (k > 0) {
    bits.add((int) (k % 2));
    k /= 2;
}
long answer = 0L;
for (int i = 0; i < bits.size(); i++) {
    if (bits.get(i) == 1) {
        answer += list.get(i);
    }
}

 

결과 코드는 다음과 같다

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

public class X와K1322 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long x = Long.parseLong(st.nextToken()), k = Long.parseLong(st.nextToken());
        br.close();
        List<Long> list = new ArrayList<>();
        for (long i = 1L; i <= Long.MAX_VALUE / 2; i *= 2) {
            list.add(i);
        }
        List<Integer> bits = new ArrayList<>();
        while (x > 0) {
            bits.add((int) (x % 2));
            x /= 2;
        }
        for (int i = bits.size() - 1; i >= 0; i--) {
            if (bits.get(i) == 1) {
                list.remove(i);
            }
        }
        bits.clear();
        while (k > 0) {
            bits.add((int) (k % 2));
            k /= 2;
        }
        long answer = 0L;
        for (int i = 0; i < bits.size(); i++) {
            if (bits.get(i) == 1) {
                answer += list.get(i);
            }
        }
        System.out.print(answer);
    }
}