[Lv.2] 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의 모든 수 ≤ 10^15

 

---

문제 풀이

 

이번 문제는 number를 2진수로 변환(binNumber)하고 for문을 돌려서 binNumber와 비교하여 다른 비트의 수가 1~2인 경우, 종료하는 방법밖에 생각이 나질 않았다. 하지만 이 방법은 O(N^2)이라고 판단했고 제한사항을 보면 모든 테이스케이스를 통과할 수 없는 풀이방식이었다.😭 그래서 1시간 고민 끝에 다른 사람의 풀이를 봤다.

문제에서 주어진 예제를 보면 짝수는 비트 1개를, 홀수는 비트 2개를 변환한다.

짝수, 홀수 모두 맨 끝자리의 0을 1로 바꾼다. 단, 홀수는 해당 위치 바로 다음 위치의 1을 0으로 변환한다.

이 규칙을 다른사람의 풀이를 통해 깨달았다.😳

 

# 진수 변환 함수
def convertNumber(number, base):
        T='0123456789ABCDEF'
        i,j = divmod(number, base) # i(몫) , j(나머지)
        
        if i==0:
            return T[j]
        else:
            return convertNumber(i,base) + T[j]
    
    
def solution(numbers):
    answer = []

    for num in numbers:
        binNumber = list('0'+ convertNumber(num,2)) # list('0' + bin(num)[2:]) 과 동일
        idx = ''.join(binNumber).rfind('0') # rfind(value): 문자열의 오른쪽부터 value를 찾는다.
        binNumber[idx] = '1'
        
        if num % 2 != 0:
            binNumber[idx+1] = '0'
        
        answer.append(int(''.join(binNumber),2)) # int(숫자, 2) : 10진수로 변환
    return answer

 

위 코드처럼, 파이썬 bin()을 쓰지않고 10진수를 2진수로 변환하는 함수를 따로 만들었다.(이 방식이 bin쓰는 것보다 빠른줄 알았다...)

이런 내 생각은 틀렸다.  아래 두 결과 사진을 보면 확연히 차이난다.!

convertNumber함수를 사용한 결과

bin()를 사용한 결과

 

 

 

---

후기

 

Lv2였지만, 생각이 많이 필요한 문제였다.

그래도 이번 문제를 통해서 진법변환 내장함수가 내가 생각했던 것보다 시간복잡도가 낮다는 것!을 깨닫는 시간이었다👍