[Programmers] 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의 모든 수 ≤ 1015

---

##### 입출력 예

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

---

##### 입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

문제 풀이

---

숫자가 짝수일 때는 1이 더 큰 수가 답이고, 홀수일 때는 아래 주석 처리한 부분의 과정으로 답을 찾는다.

# 맨 오른쪽 0을 1로 바꾸고 (없으면 맨 앞에 1을 추가)
# '바꾼 인덱스+1' 부터 오른쪽으로 탐색하여 1을 하나만 0으로 바꿈 (없으면 생략)

def solution(numbers):
    answer = []
    for num in numbers:
        # 짝수일 때
        if num % 2 == 0: 
            answer.append(num+1)
            continue
        # 홀수일 때
        binNum = bin(num)[2:]

        idx0r = binNum.rfind('0')
        if idx0r == -1: 
            binNum = '1' + binNum
            idx0r = 0
        else: binNum = binNum[:idx0r] + '1' + binNum[idx0r+1:]

        idx1r = binNum.find('1',idx0r+1)
        if idx1r == -1: answer.append(int(binNum,2))
        else: answer.append(int(binNum[:idx1r] + '0' + binNum[idx1r+1:],2))

    return answer

아래 코드는 비트 연산자 XOR(^)를 사용하여 풀이한 좀 더 간결한 코드인데, 매번 비교를 진행하기 때문에 시간초과가 발생한다.

# 시간 초과

def solution(numbers):
    answer = []
    for num in numbers:
        compNum = num
        while True:
            compNum += 1
            if bin(num ^ compNum).count('1') <= 2:
                answer.append(compNum)
                break
    return answer

[참고] 비트 연산자 (Bitwise Operator)

a = 60, b = 13 이라 가정한다.

a = 0011 1100

b = 0000 1101

Operator	Description	Example
&	AND 연산. 둘다 참일때만 만족	(a & b) = 12 → 0000 1100
|	OR 연산. 둘 중 하나만 참이여도 만족	(a | b) = 61 → 0011 1101
^	XOR 연산. 둘 중 하나만 참일 때 만족	(a ^ b) = 49 → 0011 0001
~	보수 연산.	(~a) = -61 → 1100 0011
«	왼쪽 시프트 연산자. 변수의 값을 왼쪽으로 지정된 비트 수 만큼 이동. 곱하기 2의 효과를 냄	a « 2 = 240 → 1111 0000
»	오른쪽 시프트 연산자. 변수의 값을 오른쪽으로 지정된 비트 수 만큼 이동. 나누기 2의 효과를 냄	a » 2 = 15 → 0000 1111

그럼 안녕!