[프로그래머스] (LV2) 2개 이하로 다른 비트

Python3

문제 설명

---

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

• 문제 예시와 같습니다.

풀이

---

Python

def solution(numbers):
    answer = []
    for n in numbers:
        if n % 4 == 3:
            b = '0'+bin(n)[2:]
            i = len(b)-3
            while i > 0 and b[i] == '1':
                i -= 1
            answer.append(int(b[:i] + '10' + b[i+2:],2))
        else: answer.append(n+1)    
    return answer

설명

---

접근법

해당 문제는 숨은 규칙성을 찾아내는 것이 가장 중요했다.

처음에는 n에 1씩 더하며 A^B 논리 비교로 값을 구하려 했지만, 효율성에서 실패했다.

그러다 ‘01’로 끝나는 비트와 10으로 끝나는 비트의 수는 항상 1을 더한값이 정답임을 발견했다. 이는 짝수, 그리고 나머지가 1인 수다.

규칙성

따라서 문제는 크게 다음과 같이 나눠진다.

1. 4로 나누었을 때 나머지가 3이 아닌 수 (0,1,2)
2. 4로 나누었을 때 나머지가 3인 수

1번 케이스 풀이

1번 케이스는 단순히 주어진 n값에 1을 더하면 정답이 된다.

2번 케이스 풀이

2번 케이스는 bit로 표현시 마지막 부분이 2개 이상의 1이 반복된 숫자라는 뜻이 된다(1011, 1111 등). 이때 n에 1을 더하면 차례대로 자리수가 올라가 큰 bit에 큰 변화를 가져오고, 문제 요구조건을 만족시키지 못한다.

따라서 1~2개의 변화만 가져가면서 더 큰 값을 구하려면, 끝에서부터 0이 나올때까지(없다면 숫자 첫 부분까지) 연속된 1의 비트값에 해당하는 숫자그룹에 1을 더한 값을 다시 더해야 한다.

즉, 100111 이란 비트가 있으면 끝에서부터 0이 나올때까지 연속된 1의 그룹인 111에 1을 더한 값 1000(=8)을 더해야 한다. 이는 111의 문자열 길이만큼 2를 거듭한 수로 나타낼 수 있다 ($2^3$).

또한, 최소값의 요구조건을 만족시키려면 여기서 방금 더한 1이 아닌 다른 1 값을 빼서 최소값을 만족시켜야한다. 따라서 기존 1 그룹에서 가장 컸던 값(111에서는 100에 해당하는 값 = 4)을 다시 빼야한다.

풀이 코드 결과

그런데 이는 사실상 0을 만날때까지 연속된 1의 그룹에서 맨 앞자리 01을 10으로 스왑한 결과와 동일하다.

따라서 이러한 풀이 방법이 효율성까지 만족시키는 정답이 된다.