[파이썬] 2개 이하로 다른 비트 - 월간 코드 챌린지 시즌2 [CODING TEST #28]

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

 

 

 

이 문제를 풀기 위해 전날 자기 전에 비트 연산자에 대해 정리를 했는데..

짝수면 1을 더하고, 홀수의 경우 오른쪽에서 가장 가까운 0을 찾고, 그 뒤의 1을 0으로 만드는 아이디어는 떠올렸는데,

가장 가까운 0을 찾는 과정에서 뭔가 이상한지 계속 에러가 났다. 하나쯤은 pass할 법도 한데..

 

def f(x):
    if x%2 == 0 or x == 1: # 짝수
        return x + 1
    else : # 홀수
        k = 0
        while x >= (1 << k): # 가장 낮은 0비트 찾기
            if x ^ (1 << k) == 1: # XOR : x가 0인 경우 1을 return
                break
            k += 1
        x |= (1 << k) # 0 -> 1
        x &= ~(1 << (k - 1)) # 1 -> 0
        return x
    
def solution(numbers):
    answer = []
    for number in numbers:
        answer.append(f(int(number)))
    return answer

 

비트마스킹을 사용한 다른 분들의 풀이를 살펴 보니 정말 기발했다..

최하위비트 0 혹은 1을 찾는 방법론을 알고리즘공부 글에 추가했다.

 

def f(x):
    if x%2 == 0 or x == 1: # 짝수
        return x + 1
    else : # 홀수
        last = (~n) & (n + 1) 
        return (n | last) & ~(last >> 1)
    
def solution(numbers):
    answer = []
    for number in numbers:
        answer.append(f(number))
    return answer