[프로그래머스/Lv2] 2개 이하로 다른 비트

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

프로그래머스

 

 

코드

from math import log2

def solution(numbers):
    def find_num(number):
        if number == 0:
            return 1
            
        if log2(number+1) - int(log2(number+1)) > 0:
            conv_num = format(number, 'b')
            z_index = conv_num.rfind('0')
            test = conv_num[z_index+1:]
            if test != '':
                conv_test = int(test, 2) + 1
                if (log2(conv_test) - int(conv_test)) > 0:
                    return number + 1
                else:
                    prefix = '10'
                    new_num = conv_num[:z_index] + prefix + conv_num[z_index+2:]
                    return int(new_num, 2)
            else:
                return number + 1
        else:
            conv_num = format(number, 'b')
            prefix = '10'
            new_num = prefix + conv_num[1:]
            return int(new_num, 2)
    
    answer = []
    for number in numbers:
        answer.append(find_num(number))

    return answer

 

 

설명

def solution(numbers):
    def find_num(number):
        i = 1
        while True:
            xor = bin(number ^ number+i)
            if xor.count('1') <= 2:
                return number+i
            i += 1

    answer = []
    for number in numbers:
        answer.append(find_num(number))

    return answer

이런 식으로 단순히 숫자 하나씩 더해서 비트 연산으로 비교하면 시간초과로 틀리게 된다.

제한사항에서 numbers의 수가 \(10^{25}\)까지 나오는 걸 보고 단순한 방법으로는 문제를 통과할 수 없다는 것을 눈치채야 한다.

 

노트를 꺼내서 직접 손으로 쭉 적다보면 규칙 하나가 눈에 보이게 된다.

 

그림 1

다른 숫자들은 모두 1을 더한 다음 수가 정답인데,

중간중간에 이 법칙을 따르지 않는 수들이 보인다.

 

대표적으로 3, 7, 15, 31, ... 등 2의 거듭제곱 수가 되기 1 부족한 수들이 그러한데,

이 숫자들은 2진수로 변환했을 때(1 이외의 자리는 무시한다고 할 때) 구성하는 수가 모두 1이다.

(ex. 3 -> 11  /  7 -> 111  /  15 -> 1111  /  31 -> 11111)

그렇기 때문에 1을 더한 수와의 비트 차이가 엄청나게 커져버린다.

(ex. 4 -> 100  /  8 -> 1000  / 16 -> 10000  /  32 -> 100000)

 

그렇다면 이 숫자들의 정답인 수들을 찾아보자

3, 7, 15, 31, .. 의 정답인 수들은 5, 11, 23, 47이다. 이 숫자들을 2진수 변환하면

5 -> 101  / 11 -> 1011  /  23 -> 10111  /  47 -> 101111 이다.

자세히 보면 3, 7 15, 31의 이진수 값에서 가장 앞자리 이진수를 버리고 '10'을 붙인 모양인 것을 알 수 있다.

 

이제 2의 거듭제곱 수가 되기 1 부족한 수들은 특이케이스로 처리할 수 있게 되었다.

 

이번에는 애매한 숫자들이 법칙을 따르지 않는 경우인데,

11, 19, 23, ... 같은 숫자들이다.

이 숫자들도 사실 위의 경우와 같다.

이 숫자들은 2진수 변환해보자.

11 -> 1011  /  19 -> 10011  /  23 -> 10111

그리고 가장 마지막에 등장한 0 뒤의 숫자들을 보자

각각 이진수로 11, 11, 111이다.

위에서 우리는 2의 거듭제곱이 되기 1 부족한 수들이 특이케이스라는 것을 알 수 있었다.

찾은 숫자들을 십진수로 다시 바꿔보자, 각각 3, 3, 7이다.

즉, 어떤 이진수에서 가장 마지막에 등장한 0의 뒤 이진수가 특이케이스에 걸리는 숫자라면(2의 거듭제곱이 되기 1 부족한 수) 법칙을 따르지 않는다는 것이다.

 

이 경우도 직접 적어보면 이해가 쉽다.

11 -> 1011  /  19 -> 10011  /  23 -> 10111

12 -> 1100  /  20 -> 10100  /  24 -> 11000

차이나는 비트 수가 확 늘어나게 된다.

 

이 경우에 정답을 구하는 방법은 특이케이스를 처리하는 방법과 거의 동일하다.

우선 가장 마지막 0을 찾고 그 0의 뒤가 특이케이스 숫자라면

그 숫자를 특이케이스대로 처리한다.

11 -> 101  /  111 -> 1011

그리고 이 숫자들을 원래 자리에 붙여준다. 이 때 찾은 0의 위치에서부터 붙여준다.

(ex. 11의 경우 1011 -> 1101   /   23의 경우 10111 -> 11011)

이렇게 하면 정답을 찾을 수 있게 된다.

 

이제 찾은 방법들을 코드로 구현하기만 하면 된다.

 

from math import log2

def find_num(number):
    if number == 0:
        return 1

    if log2(number+1) - int(log2(number+1)) > 0:
        conv_num = format(number, 'b')
        z_index = conv_num.rfind('0')
        test = conv_num[z_index+1:]
        if test != '':
            conv_test = int(test, 2) + 1
            if (log2(conv_test) - int(conv_test)) > 0:
                return number + 1
            else:
                prefix = '10'
                new_num = conv_num[:z_index] + prefix + conv_num[z_index+2:]
                return int(new_num, 2)
        else:
            return number + 1
    else:
        conv_num = format(number, 'b')
        prefix = '10'
        new_num = prefix + conv_num[1:]
        return int(new_num, 2)

정답을 구해주는 함수이다. 숫자가 들어오면 문제의 조건에 맞는 수를 반환한다.

 

if number == 0:
	return 1

입력된 숫자가 0이라면 1을 반환한다.

 

if log2(number+1) - int(log2(number+1)) > 0:
    conv_num = format(number, 'b')
    z_index = conv_num.rfind('0')
    test = conv_num[z_index+1:]
    if test != '':
        conv_test = int(test, 2) + 1
        if (log2(conv_test) - int(conv_test)) > 0:
            return number + 1
        else:
            prefix = '10'
            new_num = conv_num[:z_index] + prefix + conv_num[z_index+2:]
            return int(new_num, 2)
    else:
        return number + 1
else:
    conv_num = format(number, 'b')
    prefix = '10'
    new_num = prefix + conv_num[1:]
    return int(new_num, 2)

log2(number+1) - int(log2(number+1))은 number가 2의 거듭제곱이 되기 1 부족한 수 인지를 체크하기 위한 연산이다.

이 계산값이 0이라면 number+1은 2의 거듭제곱이라는 의미이다.

 

만약 계산값이 0보다 크다면

number를 2진수 변환한다.

z_index에 변환한 이진수 conv_num의 가장 마지막 '0'의 인덱스를 찾아 저장한다.

test 변수에 conv_num[z_index+1:] 문자열을 저장해둔다.

 

test 변수가 빈 문자열이 아니라면

test를 십진수 변환하여 1 더한 수가 2의 거듭제곱이 되기 1 부족한 수 인지를 체크한다.

만약 그렇지 않다면 number + 1을 반환한다.

그렇다면 prefix 변수에 '10'을 저장하고, conv_num[:z_index] + prefix + conv_num[z_index+2:]를 계산한 문자열을 new_num에 저장한다.

그 후 new_num을 십진수 변환하여 반환한다.

 

test 변수가 빈 문자열 이라면

number + 1을 반환한다.

 

log2(number+1) - int(log2(number+1))의 계산값이 0이라면

number를 2진수 변환한 값을 conv_num 변수에 저장한다.

prefix 변수에 '10'을 저장하고

prefix + conv_num[1:]를 계산한 문자열을 new_num에 저장한다.

그 후 new_num을 십진수 변환하여 반환한다.

 

answer = []
for number in numbers:
    answer.append(find_num(number))

answer는 정답을 저장해둘 리스트이다.

numbers의 숫자(number)들을 꺼내며 반복한다.

answer 리스트에 find_num(number)의 반환값들을 append해준다.

 

return answer

answer를 반환한다.