Programmers. 2개 이하로 다른 비트

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 2개 이하로 다른 비트

문제 풀이 - 탐색

탐색으로 해결하는 방법과 비트마스킹 2가지의 풀이가 있다. 필자는 탐색으로 풀었으나 이 문제에 효율성 체크 항목이 었었다면 통과하지 못했을 것이다.

n보다 크고 1-2개의 비트가 다른 수이면서 그 중 가장 작은 수이므로 끝에서부터 탐색하다가 처음으로 0을 만나는 지점에서 1로 바꾸고 그 직전의 값을 0으로 바꾸면 되겠다. 만약 뒷자리가 없으면 그대로 리턴한다.

• 주어진 수를 2진수로 변한한뒤 스트링으로 바꾸고 배열에 넣는다. 혹시 1로만 이루어진 수일 수도 있으므로 앞에 "0"을 추가해둔다.
• 뒤에서부터 탐색하여 처음으로 만나는 0을 1로 바꾸고 그 직전 값을 0으로 바꾼다. 직전 좌표가 없다면 그대로 리턴

python 코드

def solution(numbers):
    def convert(n):
        s = bin(n)[2:]
        buf = ["0"]
        for c in s:
            buf.append(c)
        for i in range(len(buf) - 1, -1, -1):
            if buf[i] == "1":
                continue
            elif buf[i] == "0":
                buf[i] = "1"
                if i < len(buf) - 1:
                    buf[i + 1] = "0"
                break
        s = "".join(buf)
        res = 0
        for i, c in enumerate(s[::-1]):
            res += int(c) * (2 ** i)
        return res

    answer = []
    for n in numbers:
        answer.append(convert(n))
    return answer

문제 풀이 - 비트마스킹

값 n에 대해 n + 1 & ~n은 n의 이진수의 0자리가 1로 변한 값이다. 이 값을 P라 하고 이 값을 n과 or 연산하면 가질 수 있는 최댓값이 된다. 1로만 구성된 값이면 n + 1로 자리수가 늘어난 길이가 갖는 최댓값으로 바뀐다.

비트 반전된 P에 대해 오른쪽으로 1비트 움직인 뒤 비트를 반전시키면 기존값과 비교해 0이 있던 자리는 1이 되고 그 다음 자리는 0이 될 상태일 것이다. 이 반전된 값을 방금 구했던 최댓값과 and 연산하면 된다.

python 코드

def solution(numbers):
    answer = []
    for n in numbers:
        p = n + 1 & ~n
        M = p | n
        p >>= 1
        p = ~p
        answer.append(p & M)
    return answer