두 개의 정수 N과 K가 주어졌을 때, 서로 다른 N개의 값을 찾아 이들을 비트별 OR(bitwise OR) 연산했을 때 그 결과가 정확히 K와 같아지도록 해야 합니다. 만약 가능한 조합이 존재하지 않는다면 -1을 반환합니다.
예를 들어 입력이 N = 4, K = 6이라면 출력은 [6, 0, 1, 2]가 됩니다. 실제로 6 | 0 | 1 | 2 = 6이므로 조건을 충족합니다.
해결 접근 방법
이 문제는 다음 단계에 따라 해결할 수 있습니다.
- MAX := 32로 설정합니다.
- visited := 크기가 MAX인 리스트를 생성하고 False로 채웁니다.
- res := 결과를 저장할 새로운 리스트를 생성합니다.
- add() 함수를 정의합니다. 이 함수는 num을 매개변수로 받습니다.
- point := 0, value := 0으로 초기화합니다.
- i를 0부터 MAX까지 반복하면서 다음을 수행합니다.
- visited[i]가 참이면 다음 반복으로 건너뜁니다.
- 그렇지 않은 경우:
- num AND 1의 결과가 참이면 value에 2^i를 더합니다.
- num := num / 2 (정수 부분만 유지)
- value를 res 리스트의 끝에 추가합니다.
메인 메서드에서는 다음 과정을 진행합니다.
- pow2 := 2^0부터 2^31까지의 2의 거듭제곱 값을 담은 배열을 생성합니다.
- res의 끝에 k를 추가합니다.
- cnt_k := k의 설정된 비트(set bit) 개수를 계산합니다.
- pow2[cnt_k] < n이면 -1을 반환합니다.
- count := 0으로 초기화합니다.
- i를 0부터 pow2[cnt_k] - 1까지 반복하면서 다음을 수행합니다.
- add(i)를 호출합니다.
- count를 1 증가시킵니다.
- count가 n과 같으면 반복문을 빠져나옵니다.
- res를 반환합니다.
여기서 핵심 아이디어는 어떤 수 x의 설정된 비트들이 K의 설정된 비트들에 포함되는 경우, x | K = K가 성립한다는 점입니다. K의 설정된 비트 개수가 cnt_k일 때 후보가 될 수 있는 값은 총 2^cnt_k개이므로, 2^cnt_k가 n보다 작으면 조건을 만족하는 N개의 서로 다른 값을 만들 수 없습니다.
구현 예시
다음 구현을 통해 더 잘 이해해 보겠습니다.
MAX = 32
visited = [False for i in range(MAX)]
res = []
def set_bit_count(n):
if (n == 0):
return 0
else:
return (n & 1) + set_bit_count(n >> 1)
def add(num):
point = 0
value = 0
for i in range(MAX):
if (visited[i]):
continue
else:
if (num & 1):
value += (1 << i)
num = num//2
res.append(value)
def solve(n, k):
pow2 = [2**i for i in range(MAX)]
res.append(k)
cnt_k = set_bit_count(k)
if (pow2[cnt_k] < n):
return -1
count = 0
for i in range(pow2[cnt_k] - 1):
add(i)
count += 1
if (count == n):
break
return res
n = 4
k = 6
print(solve(n, k))
입력
4, 6
출력
[6, 0, 1, 2]