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

🚫 Brutal Force

처음 풀이

처음에는 아래와 같이 브루탈 포스로 풀었습니다. fn을 n에서 부터 1씩 증가시켜 가면서 조건에 만족하는 fn을 찾는 것입니다. 하지만 이렇게 풀면 무조건 시간초과가 나게 되어있습니다. numbers의 길이가 최대 100,000이고 number의 최댓값은 무려 10의 15제곱이기 때문입니다.

func solution(_ numbers:[Int64]) -> [Int64] {
    
    // 비트 차이를 비교하는 함수
    func bitDiff(_ nBit: String, _ fnBit: String) -> Int {
        var nBit = nBit
        if nBit.count != fnBit.count {
            nBit = "0" + nBit
        }
        
        var cnt = 0
        
        let nArray = nBit.map { String($0) }
        let mArray = fnBit.map { String($0) }
        
        for i in 0..<nArray.count {
            if nArray[i] != mArray[i] { cnt += 1 }
        }
        
        return cnt
    }
    
    // 1씩 더하면서 비트 차이가 2 이하인 fn 값을 찾는 함수
    func f(_ n: Int64) -> Int64 {
        let nBit = String(n, radix: 2)
        var fn = n + 1
        
        while true {
            let fnBit = String(fn, radix: 2)
            if bitDiff(nBit, fnBit) <= 2 {
                return fn
            } else {
                fn += 1
            }
        }
    }
    
    return numbers.map { f($0) }
}

Bit의 규칙을 찾자

고로 이 문제를 Brutal Force로 해결할 수 있는 문제가 아닙니다. 그렇다면 Bit에 어떤 규칙이 있을 것입니다.

규칙

규칙성을 찾기 위해서 일단 몇개를 쭉 적어 보았습니다. 규칙성이 잘 보이시나요? 저는 좀 시간이 걸렸습니다. 어떤 규칙을 가지고 있는지 보도록 하겠습니다. 이 문제의 규칙의 짝수와 홀수로 나누어 보아야 합니다.

/*
 n     fn
 01    10 홀
 
 010   011 짝
 011   101 홀
 
 0100  0101 짝
 0101  0110 홀
 0110  0111 짝
 0111  1011 홀
 
 01000  01001 짝
 01001  01010 홀
 ...
 */

짝수의 경우

짝수의 경우 이진수로 표현했을 때 마지막 자리가 0입니다. 따라서 마지막 자리를 1로 바꾸어주면 즉 +1을 해주면 비트의 차이가 1인 n보다 큰 수가 됩니다.

홀수의 경우

홀수의 경우 약간 복잡합니다. 우리의 목표는 비트의 차이가 2이하로 n보다 큰 가장 작은 수를 만들어야 합니다. 짝수처럼 +1을 한다면 자릿수가 하나 올라가기 때문에 연쇄 작용으로 비트의 차이가 많이 날 수 있습니다. (ex. 111 + 1 = 1000)

따라서 최소한의 비트 차이로 숫자를 크게하려면 2의 0제곱 자리수 부터 탐색을 했을 때 (즉 문자열을 역으로 탐색을 했을때) 만나는 0을 1로 바꾸어주고 그 아래에 있는 1을 0으로 바꾸어 주어야 합니다. 쉽게 말하면 이진수 String에서 i번째 문자가 마지막 “0”이라면 i + 1의 “1”과 자리를 바꾸어 주어야 한다는 것입니다. 이렇게 하면 비트의 차이가 2인 n보다 큰 수를 만들 수 있습니다.

혹시 마지막 “0” 다음에 무조건 “1”이 온다는 보장이 있는지 확신하지 못하시는 분들이 계실 수도 있을 것 같은데요. 생각을 해보면 홀수의 이진수는 무조건 “1”로 끝나게 되어 있습니다. 즉 아무리 “0”이 뒤쪽에 있다고 하더라고 이진수 자체는 “1”로 끝나게 되어 있습니다. 따라서 마지막 “0”은 뒤에 “1”이 있다는 것을 보장할 수 있습니다.

코드

func solution(_ numbers:[Int64]) -> [Int64] {
    
    func f(_ n: Int64) -> Int64 {
        // 짝수이면 n + 1 리턴
        if n % 2 == 0 { return n + 1 }
        
        // 홀수인 경우
        
        // 맨 앞에 "0"을 붙여주어서 모든 자릿수가 "1"인 경우에 대비한다.
        var nArray = ["0"] + String(n, radix: 2).map { String($0) }
        
        // 역으로 순회하면서 마지막 "0"을 그 다음 "1"과 자리를 바꾸어 준다.
        for i in (0..<nArray.count).reversed() {
            if nArray[i] == "0" {
                nArray.swapAt(i, i + 1)
                break
            }
        }
        
        return Int64(nArray.joined(), radix: 2)!
    }
    
    return numbers.map { f($0) }
}