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

코딩테스트 연습 - 2개 이하로 다른 비트

 

한 개 혹은 두 개의 비트만 바꿔서 현재 숫자보다 큰 값중 최솟값을 찾는 문제입니다.

 

현재 숫자의 모든 비트가 1인 경우와 0이 한 개라도 존재하는 경우로 나눠서 생각하면 됩니다. 그 이유는 아래와 같습니다.

 

1) 모든 비트가 1이라면 이보다 큰 수를 만들기 위해서는 무조건 앞에 1비트를 붙이고, 그 다음에 1비트를 0으로 바꿔주는게 최선이겠죠.

 

2) 비트 중에 하나라도 0이 있다면 그 비트를 1로 바꾸는 순간 현재 숫자보다는 커지는 값이 됩니다. 따라서 되도록 작은 주소값에 있는 0비트를 1비트로 바꾸고, 만약 그 뒤로 1비트가 나타난다면 그 비트도 0으로 바꾸면 총 2개의 비트를 바꾸고 최적값을 찾을 수 있습니다.

 

이를 코드로 옮기면 아래와 같습니다.

 

[풀이]

def solution(numbers):
    answer = []
    for number in numbers:
        # number를 bit로 바꿔서 0, 1만 관찰하자
        numberBit = list(bin(number)[2:])
        zero_pos, one_pos = -1, []
        for b in range(len(numberBit)):
            # 가장 뒤쪽에 있는 0과 1의 위치 저장
            if numberBit[b] == '0':
                zero_pos = b
            if numberBit[b] == '1':
                one_pos.append(b)

        # 0이 한 개라도 존재한다면 1로 바꿀 수 있다.
        if zero_pos >= 0:
            numberBit[zero_pos] = '1'
            # 0 다음에 가장 가까운 1을 0으로 바꾼다.
            for p in one_pos:
                if p > zero_pos:
                    numberBit[p] = '0'
                    break
            numberBit = ''.join(numberBit)
        # 0이 한 개도 없으면 맨 앞에 1을 붙이고 그 다음에 1은 0으로 바꾼다.
        else:
            numberBit = '10' + ''.join(numberBit[1:])
        answer.append(int(numberBit, 2))

    return answer