[프로그래머스] 2개 이하로 다른 비트 (python)

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

프로그래머스

 

 

이 문제는 비트마스크 관련 문제이다.

 

비트 조작을 해야 하므로 2진법으로 전환해야 하니 진법 전환까지 해야 하는 것을 알 수 있다.

 

x를 만들기 위해 조건을 확인하면 x보다 크고, x와 비트가 1~2개 다른 수들 중 가장 작은 수를 만들어야 한다.

 

하지만 x와 비트가 1~2개 달라야 한다는 조건을 구현하기는 매우 어렵다.

 

그래서 x가 올 수들을 짝수와 홀수로 나누어서 생각해본다.

 

x 값이

• 짝수가 오면, 1 더해줌
• 홀수가 오면, 오른쪽으로 읽으면서 가장 먼저 나오는 0과 그 뒤에 있는 비트의 위치를 바꿔줌

 

 

코드로 작성해주면 아래와 같다.

def f(x):
    if x % 2 == 0: return x + 1

    # f-string을 사용해 문자 포맷팅, f''
    # f'0{}'은 2진수 값 앞에 0을 붙임. ex) 5 -> 0101
    x = f'0{bin(x)[2:]}' # 중괄호 안, 슬라이싱으로 순수하게 2진수 값만 남김

    # 10 왼쪽: 마지막 0이 나오기 이전의 비트들
    # 10 오른쪽: 마지막 0이 나오고 난 위치에서 2개 이후의 나머지 비트들
    x = f"{x[:x.rindex('0')]}10{x[x.rindex('0') + 2:]}"

    # 2진수 -> 10진수 변환
    return int(x, 2)

def solution(numbers):
    # 리스트 numbers의 각 요소 number에 대해 함수 f를 호출
    # 결과는 새로운 리스트로 만듬 (in numbers)
    return [f(number) for number in numbers]

 

홀수 부분만 살펴보자면,

1. x에 10진수 값이 있으므로 2진수 값으로 변경해준다. 이 때 변경된 2진수 값 앞에 0을 붙인다. 111 처럼 0이 오지 않는 수가 있는 경우에는 0을 읽을 수가 없으므로 그런 경우에 대비해 넣어준다.
2. 그 다음에는 오른쪽에서 읽었을 때 가장 먼저 0이 나오는 수를 찾고 왼쪽과 오른쪽으로 나눈다. 그 나눠진 사이에 10을 넣고 다시 결합한다.

 

references

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

프로그래머스

 

product.kyobobook.co.kr

프로그래머스 코딩 테스트 문제 풀이 전략: 파이썬 편 | 김범수 - 교보문고