2진법 문제는 처음 풀어보는 것 같다. 평소에도 최대한 내장함수를 이용하는 편이어서, 이번에도 당연히 bin(N)을 사용하였다. N%2는 '굳이?'라는 생각이었는데 풀고나니 N%2가 더 깔끔해보였다. 12ms의 코드에서 up = up << 1은 생각지도 못했다. 당연히 up *= 2였는데.. 이번에는 생각하지 못했지만 문제를 더 많이 풀어보면 충분히 생각할 수 있을 것 같다.
처음 제출한 코드
class Solution:
def bitwiseComplement(self, N: int) -> int:
b = list(bin(N)[2:])
ll = list(map(lambda x: abs(int(x)-1) , b))
po, answer = 0,0
while ll:
n = ll.pop()
answer += n * pow(2, po)
po += 1
return answer처음 제출한 코드이다. 무려 28ms.. 단순히 2진법으로 바꾸려고만 하였는데 또 쉬운 길 어렵게 돌아간 꼴이 되어버렸다. 사실 여기서도 b와 ll을 따로 리스트로 만들지 않고 충분히 풀 수 있다.
ver. 더 깔끔
place_value = 1
while N > 0:
s += (1^N%2) * place_value
place_value *= 2
N //= 2위 처럼 XOR(^)와 나머지(%) 연산을 활용하면 간단하게 해결된다.
best (12ms)
class Solution:
def bitwiseComplement(self, N: int) -> int:
if N == 0: return 1
if N == 1: return 0
up = 2
while up <= N:
up = up << 1
return up -1 -N귀찮다고 생각만 하지말고 (손으로) 직접 풀어보고 점화식도 도출하자!
참고)
bin(5) # 0b101
int('0b101', 2) # 5