[프로그래머스] 코딩테스트 연습 - 2개 이하로 다른 비트(Python)

코딩테스트 연습 - 2개 이하로 다른 비트 [월간 코드 챌린지 시즌2]

코딩테스트 연습 - 2개 이하로 다른 비트

풀이

천천히 생각해보면 그리 어렵지 않은 문제였다고 생각되네요.

먼저 문제에서 요구하는 것은 어떠한 정수 x에 대해서 비트가 2개 이하로 다른 가장 가까운 큰 수를 찾는 것이죠. 

그럼 어떻게 가까운 큰수를 만들지부터 알아야 하는데 사실문제의 예시에 다 나와있다고 생각합니다ㅎㅎ

먼저 2진법으로 표현된 숫자에는 두가지 종류가 있습니다. 

 

(1) 모두 1로 이루어진 숫자 ex) 111(7)

먼저 (1)번처럼 모두 1로 이루어진 수와 가장 가까운 큰 수를 만들기 위해서는 어쩔 수 없이 자릿수가 추가되어야겠죠. 1만 더해도 111 + 1 = 1000처럼 자릿수가 변해버리니까요. 그래서 자릿수를 추가하는 데에 1개의 다른 비트가 사용됩니다. 그럼 남은 변경 가능한 비트는 1로 이루어진 가장 큰 자릿수를 0으로 만들어버리면 가장 큰 수를 빼주는 꼴이 되어 원래의 수와 가장 가까워집니다.

ex) 111(7) -> 1111(15) -> 1011(11)  

 

(2) 1과 0이 섞여있는 숫자 ex) 1011(11)

(2)의 경우에는 가장 오른쪽에 있는 0을 1로 바꾸어 주면 자리수를 변경하지 않고 가장 작은 수를 추가한 것이 됩니다. 그 후에 0의 바로 오른쪽에 1이 있다면 0으로 변경해서 가능한 가장 큰 수를 빼주는 꼴을 만들면 됩니다.

ex) 1011(11) -> 1111(15) -> 1101(13)

 

Code

def solution(numbers):
    answer = []
    for num in numbers:
        bnum = bin(num)[2:]
        if bnum.count('0') == 0:        # 모두 1인 경우
            nnum = '0b10' + bnum[1:]
        else:                           # 0이 포함된 경우
            idx = bnum.rfind('0')       # 오른쪽으로 부터 첫번째 0
            if len(bnum[idx+1:]) > 0:   # 0기준 오른쪽 문자열의 길이가 있을 때
                nnum = '0b' + bnum[:idx] + '10' + bnum[idx+2:]
            else:                       # 0기준 오른쪽 문자열의 길이가 없을 때
                nnum = '0b' + bnum[:idx] + '1' + bnum[idx+1:]
        result = int(nnum, 2)
        answer.append(result)
    return answer

 

 

문제 설명

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

• x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

예를 들어,

• f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

수비트다른 비트의 개수

2	000...0010
3	000...0011	1

• f(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 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ \( 10^{15} \)

입출력 예

numbers	result
[2,7]	[3,11]