f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.
f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.
정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
1 ≤ numbers의 길이 ≤ 100,000
0 ≤ numbers의 모든 수 ≤ 10^15
입출력 예
문제 풀이 1
문제를 접했을 때 가장 먼저 든 생각은 1씩 큰 값을 가져와 현재 값과 비교하는 식으로 접근
시간 복잡도를 생각하지 않고 작성한 부분이라 제한 조건을 생각하면 많이 비횰율 적인 코드
def solution(numbers):
answer = []
for number in numbers:
add_num = 1
bit_number = [ _ for _ in format(number, 'b') ]
while True :
count = 0
chek_number = [ _ for _ in format(number+add_num, 'b') ]
if len(bit_number) < len(chek_number):
bit_number.insert(0,'0')
for i in range(len(bit_number)):
if bit_number[i] != chek_number[i]:
count += 1
if count in [1,2]:
break
add_num += 1
answer.append(number+add_num)
return answer
문제 풀이 2
시간 복잡도를 줄이는 가장 빠른 방법은 위의 코드에서 필수로 들어가야 하는 첫번째 for문을 남기고 나머지 반복문을 없애야 한다
그렇다면 아래 1씩증가하면서 다른 비트가 1~2개 다른 수들 중에서 제일 작은 수 를 찾는 공식이 필요
일단 제한 사항으로 0부터 10*15까지의 입력 값이 존재
짝수이면 비트의 자리 끝이 0이므로 1증가만으로 서로 다른 비트의 개수가 1이므로 주어진 값에 1을 더하기
홀수이면 "01(1) -> 10(2), 011(3) -> 101(5), 101(5)->110(6)" 처음 만난 01을 만나면 뒤를 바꾸 10 비트수가 2개 이하인 최소 값
def solution(numbers):
answer = []
for number in numbers:
#짝수이면 비트의 자리 끝이 0이므로 1증가만으로 서로 다른 비트의 개수가 1이 됨
if number % 2 == 0:
answer.append(number+1)
else:
"""
홀수 01(1) -> 10(2), 011(3) -> 101(5), 101(5)->110(6)
처음 만난 01을 만나면 뒤를 바꾸 10 비트수가 2개 이하인 최소 값을 구할 수 잇음
"""
bit_number = list('0'+bin(number)[2:])[::-1]
for i in range(len(bit_number)):
if bit_number[i] == '0':
bit_number[i] = '1'
bit_number[i-1] = '0'
break
answer.append(int(''.join(bit_number[::-1]),2))
return answer
