[프로그래머스] 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. 후기

1 .
단순 for문을 돌리는 것은 시간초과가 발생한다. numbers의 범위를 보고 바로 캐치해야 한다.

2 .
짝수의 경우, 모든 짝수의 LSB(최하위비트)는 항상 0이다. xLSB1로 변경하면 끝이다.

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개 다른 수들 중에서 제일 작은 수
    그렇다면 어떤 01로 바꿔야만 할까? 가장 작은 수를 찾아야 하므로 LSB에서 시작하여 처음으로 만나는 01로 바뀌어야 가장 작은 값을 가질 것이다.

    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)

좋은 웹페이지 즐겨찾기