숫자 목록 nums와 정수 k가 주어졌을 때, 다음 연산을 정확히 k번 수행한다고 가정해 보겠습니다. 목록에서 임의의 숫자를 하나 선택한 뒤, 그 숫자의 이진 표현에서 값이 0인 비트를 골라 1로 바꾸는 것입니다. 모든 연산을 마친 후 얻을 수 있는 최소 합계를 구해야 하며, 결과값이 너무 커질 경우 10^9+7로 나눈 나머지를 반환하면 됩니다.
예를 들어 입력이 nums = [4, 7, 3], k = 2라면 출력은 17이 됩니다. 4의 이진 표현은 100, 3은 011, 7은 111입니다. 두 개의 비트를 1로 바꿔야 하므로 4의 비트 두 개를 채워 111, 즉 7로 만들면 됩니다. 이때 전체 합은 7 + 7 + 3 = 17입니다.
접근 방법
비트를 0에서 1로 바꾸면 해당 숫자는 반드시 커지기 때문에, 합의 증가분을 최소화하려면 가장 낮은 자리, 즉 작은 2^i 값에 해당하는 0비트부터 채우는 것이 유리합니다. 따라서 모든 숫자를 낮은 비트 자리부터 차례로 검사하면서 0인 비트를 발견할 때마다 2^i를 더하고 k를 하나씩 줄여 나가는 그리디 방식으로 문제를 해결할 수 있습니다.
- ans := 0, i := 0으로 초기화합니다.
- k가 0이 아닌 동안 다음을 반복합니다.
- nums의 각 원소 n에 대해 다음을 검사합니다.
- n의 i번째 비트가 0이라면 ans에 2^i를 더하고 k를 1 감소시킵니다.
- k가 0이 되면 내부 반복을 종료합니다.
- nums의 각 원소 n에 대해 다음을 검사합니다.
- 한 바퀴를 마치면 i를 1 증가시켜 다음 비트 자리를 검사합니다.
- 최종적으로 (ans + nums의 모든 원소의 합) mod m을 반환합니다.
구현 예제
다음 코드를 통해 실제 구현을 확인해 보겠습니다.
class Solution:
def solve(self, nums, k):
m = 10 ** 9 + 7
ans = 0
i = 0
while k:
for n in nums:
# n의 i번째 비트가 0인 경우
if (n >> i) & 1 == 0:
ans += 1 << i # 2^i만큼 합 증가
k -= 1
if k == 0:
break
i += 1 # 다음 비트 자리로 이동
return (ans + sum(nums)) % m
ob = Solution()
nums = [4, 7, 3]
k = 2
print(ob.solve(nums, k))입력
[4, 7, 3], 2출력
17동작 과정 살펴보기
i = 0일 때 4의 0번째 비트는 0이므로 ans에 1을 더하고 k는 1이 됩니다. 7과 3의 0번째 비트는 이미 1이므로 건너뜁니다. 이후 i = 1이 되면 4의 1번째 비트가 0이므로 ans에 2를 더하고 k가 0이 되어 반복이 종료됩니다. 최종적으로 (1 + 2 + 14) mod (10^9+7) = 17이 반환됩니다.
이 풀이는 각 비트 자리를 한 번씩만 훑으면 되기 때문에 효율적이며, 시프트 연산자 >>와 <<를 활용해 이진수 문자열 변환 없이 빠르게 처리할 수 있다는 장점이 있습니다.