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

문제 설명

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

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

 

예를 들어,

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

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

 

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 1015

---

입출력 예

---

입출력 예 설명

 

입출력 예 #1

• 문제 예시와 같습니다.

---

풀이 코드

def solution(numbers):
    answer = []
    for num in numbers:
        temp = bin(num)[2:]
        if temp[-1] == '0':
            answer.append(num+1)
        else:
            idx = 0
            for i in range(len(temp)-1, -1, -1):
                if temp[i] != '1':
                    idx = i
                    break
            if idx == 0:
                temp = '10' + temp[1:]
                answer.append(int(temp, 2))
            else:
                temp = temp[:idx] + '10' + temp[idx+2:]
                answer.append(int(temp, 2))
                
    return answer

우선, 브루트포스 방식은 사용할 수 없다.

주어지는 숫자는 100,000개이며, 현재 숫자로부터 1씩 올려가며 조건에 맞는지 확인하기에는

numbers에 나올 수 있는 수는 10의 15승까지이기 때문에 최악의 경우에는 시간복잡도면에서 시간초과를 벗어날 수 없다.

 

이럴때는 패턴을 찾아내야 한다. 세 가지 예시를 보자.

1) 1011 - 1100 - 1101

2) 10111 - 11000 - 11001 - 11010 - 11011

3) (0)11 - 100 - 101

 

첫 번째와 두 번째는 0이 오른쪽 끝 자리가 아닌, 중간에 위치한 경우이다.

조건에 맞는 수를 찾아보면, 첫 번째는 1011 - 1101, 두 번째는 10111 - 11011이다.

잘 보면, 0이 한 칸 오른쪽으로 이동한 것을 알 수 있다.

 

세 번째의 경우, 주어진 숫자를 이진수로 변환했을 때 모두 1로 차 있는 경우다.

이 경우도, 앞에 0비트를 넣고, 0을 한 칸 오른쪽으로 이동시키면 된다.

 

예시에 나오지 않았지만, 가장 오른쪽 비트가 0이라면 그냥 1을 더하면 된다.

이 논리에 맞게 코딩을 하면 된다.

 

python의 bin 함수를 사용하면, 쉽게 10진수를 2진수로 변경할 수 있다.

리턴 값은 문자열로, '0bxxxxx' 꼴로 나오기 때문에, 앞의 0b를 삭제하기 위해 슬라이싱으로 [2:] 부터 사용한다.

 

오른쪽부터 왼쪽으로 비트를 확인하며, '1'이 아닌 비트가 있는지 확인한다.

'1'이 아닌 비트, 즉 '0'인 비트가 존재하면 '0'비트 왼쪽은 모두 살리고, '10'으로 0과 1의 위치를 바꾸고, 두 칸을 건너뛰고 오른쪽 부분을 살린다.

 

'0'인 비트가 존재하지 않으면, 가장 앞이 '10'으로 바뀌고, 나머지 부분을 살린다.

최종 answer에 넣을 때는, 2진수를 10진수로 변환해야 하기 때문에 int 함수를 사용한다.

int의 parameter중에는, 진수를 넣을 수 있다. int(문자열, 문자열이 표현하고 있는 진수)를 넣어주면 N진수를 10진수로 변환할 수 있다.