[프로그래머스] 2개 이하로 다른 비트
https://programmers.co.kr/learn/courses/30/lessons/77885#qna
1. 전체 코드
def solution(numbers):
answer = []
for num in numbers:
temp = bin(num)[2:]
# 짝수
if num % 2 == 0:
answer.append(num + 1)
continue
# 홀수
bi = '0' + temp # 비트수 초과 방지
find = bi.rfind('0') # LSB(최하위 비트) 부터 탐색하여 처음으로 만나는 '0' 비트의 index
temp = list(bi)
temp[find] = '1'
temp[find + 1] = '0'
answer.append(int(''.join(temp), 2))
return answer
print(solution([2, 7]))
2. 후기
def solution(numbers):
answer = []
for num in numbers:
temp = bin(num)[2:]
# 짝수
if num % 2 == 0:
answer.append(num + 1)
continue
# 홀수
bi = '0' + temp # 비트수 초과 방지
find = bi.rfind('0') # LSB(최하위 비트) 부터 탐색하여 처음으로 만나는 '0' 비트의 index
temp = list(bi)
temp[find] = '1'
temp[find + 1] = '0'
answer.append(int(''.join(temp), 2))
return answer
print(solution([2, 7]))
1 .
단순 for문을 돌리는 것은 시간초과가 발생한다. numbers
의 범위를 보고 바로 캐치해야 한다.
2 .
짝수의 경우, 모든 짝수의 LSB(최하위비트)
는 항상 0
이다. x
의 LSB
를 1
로 변경하면 끝이다.
ex)
1100(x = 12)
->1101(x + 1 = 13)
홀수의 경우 111(x = 7)
, 10101(x = 21)
두 가지 경우를 생각해보자. 전자의 경우 모든 비트가 이미 1
로 되어있기 때문에 x
보다 큰 값을 표현할 수 없다. 그래서 0
을 맨 앞에 붙여서 0111
형태로 수정해야 한다. 후자는 문제가 없다.
-
첫 번째 조건
x보다 큰 수
010101(x = 21)
보다 큰 수를 찾으려면1
은 수정할 수 없다.1
을 가진 어떠한 비트든 간에0
으로 변경하면 기존의x
값보다 무조건 작아지기 때문이다. 그렇기 때문에0 -> 1
을 해야만 기존의 값보다 커야한다는 첫 번째 조건을 만족시킬 수 있다. -
두 번째 조건
비트가 1~2개 다른 수들 중에서 제일 작은 수
그렇다면 어떤0
을1
로 바꿔야만 할까? 가장 작은 수를 찾아야 하므로LSB
에서 시작하여 처음으로 만나는0
이1
로 바뀌어야 가장 작은 값을 가질 것이다.ex)
010101(x = 21)
첫 번째로 만나는 0비트를 1로 변경:010111(= 23)
--> x보다 큰 값 중 가장 작다!
두 번째로 만나는 0비트를 1로 변경:011101(= 29)
세 번째로 만나는 0비트를 1로 변경:110101(= 53)
이제 한개의 비트를 바꿨으니 한개의 비트를 더 바꿔서 값을 더 작게 만들 수 있다.
1
로 바꾼 비트의 바로 옆에 있는 오른쪽 비트를0
으로 바꾸면 된다. 상위비트(왼쪽)로 갈수록 비트가 의미하는 값이 크기때문에 최대한 왼쪽에 있는 비트를0
으로 바꿔야 값이 크게 작아지기 때문이다.010101(x = 21) -> 010111(= 23) -> 010110(= 22)
Author And Source
이 문제에 관하여([프로그래머스] 2개 이하로 다른 비트), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@legowww/프로그래머스-2개-이하로-다른-비트저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)