[프로그래머스] 월간 코드 챌린지 시즌2 5월. 2개 이하로 다른 비트

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

코딩테스트 연습 - 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

 

입출력 예

 

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

 

풀이

bi_num = str(bin(number)[2:].zfill(100))
            next_num = number
            while True:
                next_num += 1
                bi_next_num = str(bin(next_num)[2:].zfill(100))
                count = 0
                for i in range(99, -1, -1):
                    if bi_num[i] == bi_next_num[i]:
                        continue
                    else:
                        count += 1
                        if count > 2:
                            break

                if count <= 2:
                    break
            answer.append(next_num)

실제로 입력 받은 숫자(number)를 bin()을 이용하여 2진수로 변환하여 저장해두고
number를 1씩 증가시키면서 하나하나 비교하면서 찾았다.
답은 나오지만 시간이 너무 오래걸려서 timeout이 나오는 방법이였다.

 

지금 number만을 가지고 찾을 방법을 생각하다가 가장 먼저 나온 0인 비트를 1로 바꾸면 될 것 같다고 생각했다.

하지만 이 경우에서는 가장 먼저나온 0을 1로 바꾸면 1111로 15의 값이 나온다 11을 만들기 위해서는 가장 먼저 나온 0을 1로 바꾸고 바로 직전의 1을 0으로 바꾸면 7 + 8 - 4 (11)로 2개의 비트만 바뀌는 최소값을 구할 수 있다.

 

def solution(numbers):
    answer = []
    for number in numbers:
        bi_num = list(str(bin(number)[2:]))
        flag = 0
        plus_two = 1
        for i in range(len(bi_num)-1, -1, -1):
            if bi_num[i] == '1' :
                continue
            else :
                bi_num[i] = '1'
                if i != len(bi_num)-1:
                    bi_num[i+1] = '0'
                flag = 1
                break
        if flag == 0:
            while plus_two*2 <= number:
                plus_two *= 2
            answer.append(number+plus_two)
        else:
            bi_num = '0b'+''.join(map(str,bi_num))
            temp = int(bi_num,2)
            answer.append(temp)


    return answer

2진수로 변경한 number을 끝에서부터 확인하면서 0이 나오면 현재 비트를 1 이전 비트를 0으로 변경한다.
하지만 맨 끝의 비트가 0인 경우(ex 10)가 있기 때문에 i의 위치가 처음인지 체크했다.

모든 비트가 1인 경우(ex 111)에는 맨 앞에 1을 추가하고 바로 다음 비트를 0으로 변경해야하기 때문에 number보다 크지 않은 2의 n승을 더해주었다. (7인 경우에는 +8 -4 는 +4와 같다.)

만들어진 비트는 리스트에 저장되어 있기 때문에 처음에 제거했던 '0b'를 넣고 다시 10진수로 변환해주었다.