[프로그래머스] 2개 이하로 다른 비트 - 파이썬

https://programmers.co.kr/learn/courses/30/lessons/77885

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

문제 설명

2개 이하로 다른 비트

 

양의 정수 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

 

입출력 예

---

문제 풀이

처음 문제를 봤을때 자연수를 2진수로 만들어 비트를 비교해주면 쉽게 구할 수 있을거라고 생각하고 접근했다.

자연수를 2진수로 변환해서 (7 -> 0111) 비트가 1~2개 다른 수들 중에서 제일 작은 수를 구하는 것이 문제였다.

 

가장 먼저 떠올린 로직은 해당하는 숫자에 1씩 증가시키며, 증가한 수를 2진수로 바꾸고 두 이진수 비트를 비교하는 것이었다. 파이썬 bin 함수를 쓰게되면 0111이 아닌 111의 형태로 나오게 되는데 비교하는 숫자와 자리수를 맞추기 위해 비교하는 숫자의 길이만큼 최상위 비트에 0을 추가해준다(# 자리 수 맞추기)

 

 2진수는 하위 비트부터 비교해야 하므로 리스트의 마지막 원소부터 비교한다. 원래의 수(bin_num)보다 1 증가한 수(cmp_num)과 다른 비트의 개수를 cnt 변수로 체크하고 cnt가 2개 이하이고 0보다 크면 증가시킨 수(cmp_num)을 추가한다.

 

그러나 테스트 케이스 10번, 11번이 시간 초과가 발생하여 통과하지 못하였다.

문제의 조건에서 numbers의 최대 값이 10^15이니 1씩 더해가며 탐색하는 경우 시간초과가 발생하는 것이다.

# TC 10,11 시간초과
def solution(numbers):
    answer = []
    
    for num in numbers:
        if num % 2 == 0:
            answer.append(num+1)
            continue

        bin_num = list(bin(num)[2:])
    
        while True:
            num += 1
            cmp_num = list(bin(num)[2:])

            N = len(cmp_num)

            if len(bin_num) != N:       # 자리 수 맞추기
                diff = N - len(bin_num)
                for _ in range(diff):
                    bin_num.insert(0, '0')

            cnt = 0
            for i in range(N-1, -1, -1):
                if bin_num[i] != cmp_num[i]:
                    cnt += 1

            if cnt <= 2 and cnt != 0:
                answer.append(num)
                break
            
    return answer

 

그러므로 비트를 인덱싱하여 검색하는 방법으로는 시간 초과를 해결하지 못하였고, 동아리 내에서 같이 스터디하는 분들의 아이디어를 참고하여 답을 구할 수 있었다.

---

문제를 해결하는데 가장 핵심인 아이디어는 2진수로 나타낸 비트에서 0의 위치를 판단하는 것이다.

2진수로 나타낸 비트를 3가지의 케이스로 구분할 수 있다.

 

1. 모든 비트가 1인경우
2. 마지막 비트가 0인경우 (짝수인 경우)
3. 마지막 비트가 1이고, 모든 비트가 1이 아닌 경우 (홀수이면서 모든 비트가 1이 아닌 경우) 

 

우선 1번 경우를 생각해보면 11111111보다 큰 수 이고 비트가 1~2개 다르면서 가장 작은 수는 최상위 비트를 0으로 바꾼 후 최상위 비트의 왼쪽에 1을 추가해준다. 즉 101111111 은 비트를 2번 변경한 수 중 가장 작은 수이다.

 

2번의 경우에는 마지막 비트가 0이므로 짝수에 해당하는 경우이다. 따라서 마지막 비트만 1로 바꿔주면 비트가 1~2개 다르면서 원래의 수 보다 큰 수 중 가장 작은 수이다.

 

3번의 경우에는 10000111을 생각해보자. 10000111보다 큰 수 중 비트를 1~2번 변경하기 위해서는 마지막으로 0이 나타난 위치를 찾는다. 마지막으로 0이 나타난 위치를 찾아보면 하위 비트에서 부터 4번째 비트를 찾을 수 있다. 해당 비트를 1로 바꾸고 해당 비트보다 한 자리 아래에 있는 비트를 0으로 바꾸면 답을 찾을 수 있다.

 

조금 더 케이스를 줄여보면 1, 3번의 경우를 한번에 처리할 수 있다.

모든 케이스를 처리하기 전, 최상위 비트 보다 하나 큰 자리에 0을 추가하고 시작하면 된다.

그렇게하면 자연스럽게 1,3번이 같은 케이스가 되고 보다 간결한 코드를 작성할 수 있다.

 

생각지도 못했는데 좋은 아이디어였다 ! 역시 다양한 사람들끼리 의견을 주고받으면 좋은 아이디어가 나오는 것 같다.

def solution(numbers):
    answer = []
    
    for num in numbers:
        bin_num = list(bin(num)[2:])
        
        bin_num.insert(0,'0')
        
        ind = 0
        N = len(bin_num)
        for i in range(N):
            if  bin_num[i] == '0':
                ind = i
        
        if ind == N-1: # 가장 마지막 원소가 1인 경우
            bin_num[ind] = '1'
            
        else:
            bin_num[ind] = '1'
            bin_num[ind+1] = '0'
        
        
        # 제곱근 계산
        j = 0
        res = 0
        for i in range(N-1, -1, -1):
            if bin_num[i] == '1':
                res += 2**j
            j+=1
        answer.append(res)
        
    return answer