2개 이하로 다른 비트 - 월간 코드 챌린지 시즌2
문제 소개
양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.
- x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수
예를 들어,
- f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.
수 비트 다른 비트의 개수
2 000...0010
3 000...0011 1f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.
수 비트 다른 비트의 개수
7 000...0111
8 000...1000 4
9 000...1001 3
10 000...1010 3
11 000...1011 2정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.
시나리오
1부터 2진수로 변환하여 찾아나갔다.
- 맨 마지막 비트가 ‘0’이라면 ‘1’로만 바꿔준다. 1개의 비트를 바꿈과 동시에 제일 작은 수가 된다.
-
맨 마지막 비트가 ‘1’이라면 ‘01’로 이루어진 부분을 찾아 ‘10’으로 바꿔준다. 2개의 비트를 바꾼다.
- 0111 이라면 1011로 바꾼다. f(7) = 11이다.
- 11100010111 이라면 11100011011으로 바꾼다.
-
11111과 같이 1 비트로만 구성된 경우를 대비하여 모든 비트의 앞에 0을 추가함으로서 01을 찾을 수 있도록 하였다.
- 011111 -> 101111
문제 풀이
# 2진수 변환
def dec_to_bin(n):
if n == 0:
return '0'
bin = ''
while n // 2 > 0:
bin = str(n % 2) + bin
n = n // 2
return "1" + bin
# 10진수 변환
def bin_to_dec(bin):
digit = 1
dec = 0
for s in reversed(bin):
if s == '1':
dec += digit
digit *= 2
return dec
def solution(numbers):
answer = []
for number in numbers:
bin = "0" + dec_to_bin(number)
if bin == '00':
answer.append(1)
continue
if bin[-1] == '0':
answer.append(bin_to_dec(bin[:len(bin)-1]+'1'))
continue
new_bin = ''
for s in reversed(range(1, len(bin))):
if bin[s-1:s+1] == "01":
new_bin = bin[:s-1] + "10" + bin[s+1:]
break
answer.append(bin_to_dec(new_bin))
return answer![KU_SANG [RESUME]](/static/3e9f23c883a3beeb51ecbe4e0bb7b964/a12fc/profile.png)