[Swift 알고리즘] 프로그래머스_2개 이하로 다른 비트

 

 

해결 방법: 

 

String(number, radix: 2) -> Int를 2진수로 String으로 변환

Int(binaryNumber, radix: 2) -> 2진수 String을 10진수 Int로 변환

이 두가지 방법을 통해서 문제를 풀었음

 

첫번 째 해결방법은 브루스트 포스로 1씩 더해서 풀었는데 시간초과 남

 

두번 째 해결 방법은 2차이가 언제 발생하는지 곰곰하게 생각해봄

- 원하는 수 + 1 의 이진수 값이, 원래 수의 이진수 값과 자릿수가 다를 때 0을 앞에 붙여준다.

eg) 3 -> 11, 4 -> 100 이럴경우 011로 바꿔준다.

- 타겟 값보다 크면서 && 비트가 최대 2개까지 다른 값이 목표

- 그렇게 생각하니 앞부분을 바꾸는 것 보다(2^이 올라가는 부분) 뒷부분을 바꾸는 방식이 값 차이가 덜 나는방법이라고 생각했음

- 앞 부분과 뒷 부분을 어떤 방식으로 나눌까 고민했는데, 비트기준으로 0이 뒷쪽(오른쪽)에 있는 것들은 건드려서 바꾸면 최적의 해라고 결론 지음

- 아래는 예시임

// 1000
// 1001
맨 뒤에 0이 있음 맨 뒤 0을 1로 바꿈
// 1 1100 0111
// 1 1100 1011
중간에 0이 있음. 2진수 비트중에서 0이 제일 뒷쪽에 있는 0을 선택하고 바로 그 다음 index까지 변환함. 이유는 최대 2개의 비트가 다르게 만들어야 하며, 가장 적은 값 차이를 완성시켜야 함.
// 111 0111
// 111 1011

// 0111
// 1011

// 0 1111
// 1 0111

 

 

import Foundation

func solution(_ numbers:[Int64]) -> [Int64] {
    return numbers.map{getNum($0)}
}

func c2(_ number: Int64) -> String {
    return String(number, radix: 2)
}

func c10(_ number: String) -> Int64 {
    return Int64(number, radix: 2)!
}

func getNum(_ number: Int64) -> Int64{
    let tempNum2 = c2(number + 1)
    var targetNum2 = c2(number)
    if tempNum2.count != targetNum2.count {
        targetNum2 = "0" + targetNum2
    }
    var res = targetNum2.map{String($0)}
    let lastIndex = res.enumerated().filter{$0.element == "0"}.last!.offset
    res[lastIndex] = "1"
    if lastIndex !=  targetNum2.count - 1{
        res[lastIndex + 1] = res[lastIndex + 1] == "0" ? "1" : "0"
    }
    return c10(res.joined())
}