알고리즘 코드카타 101 - 2개 이하로 다른 비트

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

프로그래머스

 

양의 정수 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진수)로 전환해서 반복문을 사용해서 다음 숫자들과 하나씩 비교하는 것이었다. 다만 그렇게 하면 각 숫자별로 모든 인덱스를 비교하는 연산을 최대 10만번이나 반복해야하기 때문에 시간이 상당히 오래 걸릴 것 같았다. 그래서 접근 방법을 바꿔보았다.

 

입력되는 숫자가 짝수라면, 2진수로 변환했을 때 맨 끝자리(가장 오른쪽 자리)가 0이 된다. 따라서 올림이 발생하지 않기 때문에 number + 1을 출력하게 된다. 따라서 모든 짝수에 대해서는 긴 연산과정을 거칠 필요 없이 number + 1을 입력해주면 된다. 단순하게 생각하면 전체 시간의 절반을 줄일 수 있었다.

 

홀수인 경우를 고려해보자. 입력된숫자가 홀수라면, 맨 끝자리가 1이고 한자리가 증가하면 올림이 발생한다. 그렇다면 올려진 숫자는 얼마나 바뀔까?

x	x(2진수)	x+1	f(x)	f(x)2진수)
3	11	100	5	101
5	101	110	6	110
7	111	1000	11	1011
9	1001	1010	10	1010
11	1011	1100	13	1101
13	1101	1110	14	1110
23	10111	11000	27	11011
27	11011	11100	29	11101

 

여기까지 확인을 해보니 규칙이 눈에 보였다. 홀수인 경우,  2^( 가장 오른쪽의 1의 갯수-1)만큼 증가한다는 것을 알 수 있었다. 1이 더해지면서 0이 나올 때까지 올림을 반복하기 때문이다. 그래서 오른쪽부터 세어서 처음으로 0이 나타나는 위치까지 숫자가 바뀌게 된다. 반대로 말하면 처음으로 나타나는 0의 왼쪽부분은 원래 숫자와 같은 부분이기때문에 고려할 필요 자체가 없다. 즉, 27(11011)과 3(11)은 같은 숫자를 더해서 출력하면 된다는 것이다.

 

이제 위의 방법을 따라서 파이썬 코드를 작성해보자.

가장 먼저 2진수로 변환할 수 있는 함수를 작성해준다.

def decimal_to_binary(decimal_number):
    if decimal_number == 0:
        return "0"
    
    binary_number = ""
    
    while decimal_number > 0:
        remainder = decimal_number % 2
        binary_number = str(remainder) + binary_number
        decimal_number = decimal_number // 2
    
    return binary_number

 

 

다음으로 결과를 출력할 solution함수를 작성하고 짝수인 경우를 미리 계산한다.

def solution(numbers):
    answer = []
    for number in numbers:
        if number % 2 == 0:
            answer.append(number+1)
        else:
            #홀수작성란
    
    return answer

 

 

number가 짝수인 경우 즉시 계산을 하고 홀수인 경우에는 위의 규칙에 따라 2^(오른쪽의 1의 갯수 - 1)만큼 증가하도록 작성을 하면 된다. 파이썬의 리스트는 기본적으로 왼쪽부터 문자를 탐색하기 때문에 가장 오른쪽의 0을 찾기 위해서는 문자열을 뒤집어줄 필요가 있다. 순서대로 작성을 해보자면

1. 입력숫자를 2진수로 바꾼다

2. 2진수를 뒤집는다.

3. 뒤집은 숫자에서 첫번째 0의 인덱스를 반환한다. (0의 인덱스는 0부터 세기 때문에 1의 갯수와 일치한다.)

4. 0이 없다면 2진수의 길이를 반환한다.

5. number에 2^(1의 갯수-1)를 더한다.

	else:
		#홀수입력부분	
            binary_number = decimal_to_binary(number)
            reversed_binary = binary_number[::-1]
            number_of_one = reversed_binary.find('0')
            if number_of_one == -1:
                len_one = len(binary_number)
            else:
                len_one = number_of_one
            answer.append(number+(2**(len_one-1)))

 

 

홀수부분은 이렇게 작성되었다.

 

 

def solution(numbers):
    answer = []
    for number in numbers:
        if number % 2 == 0:
            answer.append(number+1)
        else:
            binary_number = decimal_to_binary(number)
            reversed_binary = binary_number[::-1]
            number_of_one = reversed_binary.find('0')
            if number_of_one == -1:
                len_one = len(binary_number)
            else:
                len_one = number_of_one
            answer.append(number+(2**(len_one-1)))
    
    return answer

decimal_to_binary(decimal_number)를 제외한 전체 부분은 이런 모양이다. 이제 제대로 작동이 되는지 확인해보자.

 

통과!