boj 1322: X와 K

두 자연수 X와 K가 주어진다. 그러면, 다음 식을 만족하는 K번째로 작은 자연수 Y를 구하는 문제이다.

X + Y = X | Y

 

| 가 OR 비트연산이므로 2진수로 생각해보자.

 

예제 X = 5 = 101(2)

101 + Y = 101 | Y 의 경우 X의 0이 있는 부분이 1인 경우 Y가 된다. 가능한 Y값을 크기순으로 나열하면 아래와 같다.

문제 풀이 방법은 위와 같이 X가 1, 0인 부분을 저장해 두고 1인 부분은 건너뛰면서 다음으로 가능한 수를 찾아준다.

y 값은 1을 넘어갈 수 있다고 했으니 long 범위로 설정해준다면 8byte = 64bit일 것이고, 이를 배열에 담아준다.

 

x, k를 2진수로 바꿔서 배열에 거꾸로 저장한 후 0인 비트를 해당 자리 수 만큼 쉬프트한다.

이를 구현한 코드는 아래와 같다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		long x = in.nextLong();
		long k = in.nextLong();

		int binX[] = new int[65];
		int binK[] = new int[65];

		int i = 0;

		while (x != 0 || k != 0) {
			binX[i] = (int) (x % 2);
			binK[i] = (int) (k % 2);
			x /= 2;
			k /= 2;
			i++;
		}

		int xIndex = 0, kIndex = 0;
		long y = 0;

		while (kIndex < i) {
			if (binX[xIndex] == 0) {
				y |= (1L << xIndex) * binK[kIndex++];
			}
			xIndex++;
		}

		System.out.println(y);
	}
}