[백준] X와 K 파이썬 풀이

※ 사용언어 : 파이썬 ※

 

▼ 문제 링크 ▼

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

1322번: X와 K

 

---

 

문제 접근

◇ X와 K의 범위가 20억보다 작거나 같은 자연수로 상당히 범위가 큽니다. 해당 수의 범위를 생각하면 시간 복잡도에 N이 들어가면 2초 안에 문제를 풀기는 거의 불가능하다고 볼 수 있습니다. 그러므로 상수 시간 내에 문제를 해결할 수 있는 방안을 모색해야 합니다.

 

◇ int형의 표현 범위는 대략적으로 21억 정도입니다. 즉 X와 K는 int형 범위 내의 수라는 것을 알 수 있습니다. 또한, int형은 4byte=32bit이므로, X와 K는 32bit를 넘지 않는다는 것도 알 수 있습니다. 그렇기 때문에 X와  K를 합쳐도 64bit 안에서 연산이 이루어질 것임을 알 수 있습니다. 이를 통해 최대 bit 범위를 64로 잡으면 된다고 유추할 수 있습니다. 

 

◇ X+Y = X | Y라는 식을 만족하기 위해서는 X를 2진수로 바꿨을 때, 0의 위치를 알아야 합니다.

예를 들어 X = 5인 경우,

해당 표처럼 표현할 수 있습니다.

가장 첫 번째로 등장하는 0의 자리는 10진수 2 자리입니다. Y = 2라고 가정해 봅시다.

X + Y = 5 + 2 = 7이고 X | Y = 111(2) = 7 이 됩니다. 두 연산 모두 결괏값이 7이므로, X + Y와 X | Y의 값이 같습니다. 해당 연산이 도출되는 건 너무나도 당연한 일입니다.  두 개의 수를 or 연산을 하게 될 때, 각 자릿수에 한 bit라도 1이면 해당 자릿수의 bit는 1이 됩니다. 위에 예시처럼, X의 입장에서는 10진수 2의 자리는 0이지만, Y의 10진수 2의 자리는 1입니다. or 연산을 하게 되면 결괏값은 X +2가 되게 됩니다. 이때 2는 Y의 값이고 X + Y = X | Y가 성립하게 됩니다.

 

◇ X를 2진수로 바꾸었을 때, 0이 있던 자리를 1로 바꾸게 되면 조건에 만족하는 Y값입니다.

여기서 한 가지 사실을 도출해 낼 수 있습니다. 첫 번째로 등장한 0이 있는 자리에 1을 넣은 수가 식을 만족하는 첫번째 수가 된다는 겁니다. 

위에 서술한 예시를 봅시다. Y = 2 일 때 처음으로 식을 만족하는 수가 등장하게 됩니다. 그럼 다음 수는 2 다음 0의 자리를 가지는 8이 됩니다.

 

 

◇ 위에서 설명한 내용을 종합하여 정리하자면 다음과 같습니다.

X와 K의 범위가 크기 때문에 상수시간 안에 문제를 해결해야 합니다. 이때, 연산된 값의 범위는 64bit를 넘지 않기 때문에, O(64) 시간 복잡도로 문제를 해결할 수 있습니다. O(64) 시간 안에 X의 2진수 중 0이 있는 자릿수를 찾습니다.

 

 

 

---

 

문제 풀이 (With Python)

import sys

X, K = map(int, sys.stdin.readline().split())

bin_x = format(X, "b")
x_64 = bin_x[::-1]
x_length = len(bin_x)

for a in range(64 - x_length + 1):
    x_64 += "0"

pos = []
for b in range(65):
    if x_64[b] == "0":
        pos.append(b)

bin_k = format(K, "b")
k_64 = bin_k[::-1]
k_length = len(bin_k)
for a in range(64 - k_length + 1):
    k_64 += "0"

result = [0 for _ in range(65)]
for idx in range(65):
    if k_64[idx] == "1":
        result[pos[idx]] = 1

convert = ''.join(map(str, result))
answer = int(convert[::-1], 2)
print(answer)

◇ X를 2진수로 변환합니다. 이때 2진수로 변환된 bin_x는 문자열이기 때문에 [::-1]을 이용해 bin_x를 역순으로 뒤집습니다. 문자열을 뒤집는 이유는 사람이 편하게 보기 위해서입니다. 일반적으로 한국인이라면 왼쪽에서 오른쪽으로 읽습니다. 즉 100이라는 2진수가 있다고 하면 1이 있는 자릿수가 가장 큰 자릿수이지만, 컴퓨터의 index의 기준에서 보면 1은 가장 작은 index값인 0을 가집니다. 그렇기 때문에 헷갈리는 걸 방지하기 위해 뒤집어주었습니다.

이후 bin_x를 64bit로 만들기 위해 남은 칸은 전부 0으로 채워주었습니다.

 

◇  64bit로 맞춰준 2진수 X를 순회하며 0이 위치한 자리를 찾아 pos 리스트에 넣어줍니다.

 

◇ K도 X에서 했던 작업과 똑같이 해줍니다.

 

◇ result 값을 구하는 곳을 설명하기 위해 예제 3번을 예시로 들겠습니다. 예시 3번을 가지고 위에 코드를 실행하면 결괏값은 해당 이미지처럼 나오게 됩니다.

해당 값을 가지고 for문을 탐색합니다.

idx = 0일 때,

k_64 [0] = 1 이므로, result[pos [idx]] = 1이 되게 됩니다. 여기서 pos[idx] = pos [0] = 0 이므로 result [pos [idx]] = rseult [0] 이 된다는 걸 알 수 있습니다. result [0] = 1로 바꾸고 다음 단계로 넘어갑니다.

idx = 1 일 때,

k_64 [1] = 1 이므로,  result[pos[idx]] = 1이 되게 됩니다. 여기서 pos [idx] = pos [1] = 2 이므로 result [pos [idx]] = rseult [2] 이 된다는 걸 알 수 있습니다. result [2] = 1로 바꾸고 다음 단계로 넘어갑니다.

idx = 2 일 때, 

k_64 [1] = 0 이므로,if 조건문을 만족하지 않아 넘어가게 됩니다. idx = 3 또한 if 조건문을 만족하지 않으므로 넘어가게 됩니다. 

idx = 4부터는 k_bin을 64bit로 맞춰주기 위해 0으로 채워져 있고, if 조건문을 더는 만족하지 않는다는 걸 알 수 있습니다.

 

해당 for문을 순회하고 난 뒤 result는 0번째 자리와 2번째 자리만 1인 상태가 되게 됩니다. 즉 아래 그림과 같은 상태가 되게 됩니다.

2진수인 result값을 10진수로 바꾸게 되면 5가 되게 되고 실제로 예시 출력 값 또한 5입니다.

 

마지막으로 result값을 10진수로 바꿀 수 있게 문자열로 바꿔줍니다. 그리고 뒤집어서 계산했기 때문에 다시 뒤집어서 원래 상태로 바꿔줍니다. 원래상태로 돌아온 2 진수값을 10진수로 바꾸면 원하는 결괏값을 얻게 됩니다.