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

 

▼ 문제 링크

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

 

이 문제는 많은 시행 착오 끝에 내가 생각한 일반적인 방법(비트가 1개 혹은 2개가 다른 모든 경우의 수를 비교하는 방법)으로는 효율성 테스트를 통과할 수 없다는 것을 깨닫고 결국 집단 지성의 힘을 빌린 문제였다.

내가 처음 생각했던 방법으로는 정확성은 통과한 거 같은데 효율성에서 막히더라 🥲

 

아무튼 찾아본 바로는 풀이 방법이 다음과 같다.

 

주어진 숫자가 짝수일 때

짝수를 비트로 바꾸면 1 0 0 0 (= 8)처럼 맨 마지막 비트가 0이 된다.

이때, 비트가 1개 또는 2개가 다르면서 가장 작은 수 = 자연스럽게 마지막 비트 0을 1로 바꾼 수가 된다.

즉, 주어진 수에서 1만 더해주면 된다.

 

주어진 숫자가 홀수일 때

홀수에서는 조금 복잡해진다.

어쨋거나 구하는 값은 조건을 만족하는 수 중에 가장 작은 수이기 때문에 가장 낮은 자리에 있는 비트만 바꿔주면 된다.

여기서 다른 비트가 1개가 아니라 2개까지 허용이 되는 이유가 생긴다.

예를 들어, 주어진 수가 1 0 0 1 (= 9)라고 했을 때, 조건을 만족하는 가장 작은 수는 1 0 1 0 (= 10)이다.

두 비트의 차이를 살펴보면 다음과 같다.

가장 낮은 자리에 있는 0비트를 1로 바꿔주고, 바로 뒤 비트 1을 0로 바꾼다.

어쨋든 숫자는 커져야 하니까 0을 1로 바꾸고, 가장 작아야 하니까 바꾼 비트의 뒤에 있는 비트를 1 -> 0으로 바꿔준다.

이렇게 되면 주어진 수와 2개의 비트가 다르게 된다.

 

주의해야할 점은, 1 1 1처럼 0비트가 없는 경우는 앞에 비트 1을 추가해주고 그 바로 뒤 비트를 0으로 바꿔줘야 한다는 것!

1 1 1 -> 1 0 1 1

 

 

import Foundation

func solution(_ numbers: [Int64]) -> [Int64] {
    var result: [Int64] = []
    
    numbers.forEach{ number in
        var bits = convertInt64ToBits(number)
        
        // number가 짝수일 때
        if number % Int64(2) == 0 {
            result.append(number + 1)
        // number가 홀수일 때
        } else {
            var index = 0
            
            while index < bits.count {
                if bits[index] == 0 {
                    bits[index] = 1
                    bits[index-1] = 0
                    break
                } else {
                    index += 1
                }
            }
            
            // bits에 0이 없을 때
            if index == bits.count {
                bits[index-1] = 0
                bits.append(1)
            }
            
            result.append(convertBitsToInt64(bits))
        }
    }
    
    return result
}

func convertInt64ToBits(_ number: Int64) -> [Int] {
    var bits: [Int] = []
    var num = number
    
    repeat {
        bits.append(Int(num % Int64(2)))
        num = (num / Int64(2))
    } while num != 0
    
    return bits
}

func convertBitsToInt64(_ bits: [Int]) -> Int64 {
    var result: Int64 = 0
    
    for (index, value) in bits.enumerated() {
        if index == 0 {
            result += Int64(value)
        } else {
            var multi: Int64 = 1
            
            for _ in 0..<index {
                multi *= Int64(2)    
            }
            
            result += (Int64(value) * multi)
        }
    }
    
    return result
}