10진수로 표현된 숫자가 하나 주어졌다고 가정해 봅시다. 이 숫자를 2진수 형태로 변환한 뒤 각 비트를 반전시켜 보수(complement)를 구하고, 그 결과를 다시 10진수로 바꿔 반환하는 것이 목표입니다.
예를 들어 숫자가 20이라면, 2진수 표현은 10100입니다. 각 비트를 반전하면 01011이 되고, 이를 다시 10진수로 변환하면 11이 됩니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 숫자 n의 2진수 문자열을 s에 저장합니다. (Python의 bin() 함수는 '0b10100'처럼 접두사 '0b'를 포함한 문자열을 반환합니다.)
- 합계를 담을 변수 sum은 0으로, 자릿값을 나타내는 변수 num은 1로 초기화합니다.
- s의 각 문자를 뒤에서부터(오른쪽에서 왼쪽으로) 순회합니다.
- 현재 문자 i가 'b'라면, 2진수 접두사의 끝에 도달한 것이므로 지금까지 계산된 sum을 반환합니다.
- 현재 문자 i가 '0'이라면, 반전 시 '1'이 되므로 해당 자릿값 num을 sum에 더합니다.
- 각 반복이 끝날 때마다 num을 2배로 곱하여 다음 자릿값을 준비합니다.
구현 예제
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
class Solution(object):
def bitwiseComplement(self, N):
s = str(bin(N))
sum = 0
num = 1
for i in s[::-1]:
if i == "b":
return sum
elif i == "0":
sum += num
num *= 2
ob1 = Solution()
print(ob1.bitwiseComplement(20))동작 원리 살펴보기
입력값 20의 경우, bin(20)은 문자열 '0b10100'을 반환합니다. 이 문자열을 뒤집으면 '00101b0'이 되며, 오른쪽부터 순회하게 됩니다.
- '0' → 반전 시 1이므로 sum = 0 + 1 = 1, num = 2
- '0' → 반전 시 1이므로 sum = 1 + 2 = 3, num = 4
- '1' → 반전 시 0이므로 더하지 않음, num = 8
- '0' → 반전 시 1이므로 sum = 3 + 8 = 11, num = 16
- '1' → 반전 시 0이므로 더하지 않음, num = 32
- 'b' → 접두사 끝에 도달, sum = 11 반환
입력
20
출력
11
복잡도 분석
이 알고리즘은 숫자의 2진수 자릿수에 비례하여 실행되므로 시간 복잡도는 O(log N)이며, 추가로 사용하는 공간 역시 2진수 문자열 저장을 위해 O(log N)입니다.