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

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

 

문제

양의 정수 x에 대해 함수 f(x)는 다음과 같습니다.

👉 x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

정수들이 담긴 배열 numbers가 매개변수로 주어집니다.

numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

 

풀이

bit를 잘 생각해봅시다.🧐

 

짝수인 경우

마지막 bit(1)가 무조건 0입니다. 그럼 숫자보다 큰데 비트가 2개 이하로 다른 수는 무엇일까요?

넵, 마지막 bit에 1을 채워준 수, 즉 1 큰 수 입니다.😊

 

홀수인 경우

1xxxxx1로 이루어져 있습니다. 그럼 이 숫자보다 큰데 비트가 2개 이하로 다른 수는 무엇일까요?

먼저 큰 수를 만들기 위해서는 반드시 bit 1을 추가해 주어야 합니다.

 

1을 채우고 싶을 때 숫자는 가장 작게 만들고 싶을 때, 1의 최적의 위치는 마지막 bit에서부터 탐색할 때

가장 먼저 나오는 0bit를 1로 만들어주면 됩니다. 이 수를 A라고 하겠습니다.😀

예를 들어, 13이 입력으로 들어왔을 때 이 숫자를 bit로 바꾸면 1101입니다.

 

처음 나오는 bit를 1로 바꿔주면 1111이고 10진수로는 15입니다.

 

이제 저희는 bit 하나를 더 변경할 수 있습니다.

위에서 처럼 1로 변경하는 건 큰수를 만들 뿐입니다. 그러니 이번에는 1인 bit를 0으로 바꿔보겠습니다.

 

어느 위치의 bit를 0으로 바꿔야 할까요? 잘못 바꾸면 주어진 숫자보다 작아질 수 있습니다.

그러니 앞에 숫자 A를 만들 때 바꿨던 bit보다 뒤에 있는 bit를 0으로 바꿔주면 됩니다.

 

이전의 예제에서 바뀐 숫자는 15, 이진수로 1111입니다.

이 숫자를 만들 때는 뒤에서 두번째 bit를 1로 바꿔주었죠. 그럼 그 bit의 뒤에 있는 bit를 0으로 바꿔주겠습니다.

결과는 1110, 10진수로 14입니다.

 

이렇게 짝수인 경우 / 홀수인 경우로 나눠 쉽게 계산할 수 있습니다.😚

이번에는 코드로 구현해보겠습니다.

 

코드

import kotlin.math.*

class Solution {
    fun solution(numbers: LongArray): LongArray {
        return numbers.map{
            var num = it
            // 짝수인 경우
            if (num % 2 == 0L) {
                num + 1L
            } else { // 홀수인 경우
                // 첫 0 bit 찾아보기
                val i = getZeroIndex(it)
                (it + (2.0).pow(i) - (2.0).pow(i-1)).toLong()
            }
        }.toLongArray()
    }
    
    fun getZeroIndex(it: Long): Int {
        var num = it
        var i = 0
        while (true) {
            if (num % 2 == 0L) {
                break
            }
            num /= 2
            i++
        }
        return i
    }
}