[Swift] [24일차] 2개 이하로 다른 비트

programmers-2개 이하로 다른 비트

문제설명

1. 주어진 숫자보다 크면서 비트가 1~2개만 다른 수 중에 제일작은 수 구하기
2. 여러개 주어지니까 그걸 배열에 넣기 ( 숫자 하나당 한문제라고 생각하면됨 )

---

문제접근

1. 문제는 반복문으로 1씩 늘려주면서 이거를 이진수로 변환
2. 둘의 비트가 어디서 다른지를 파악 가능해야함

Swift에서 2진수로 변환하는 방법은
String(숫자, radix:바꾸고싶은 진수 Int) 이렇게 써주면 되니까 이를 활용하고자 했는데, 이렇게 하니까

7변환 -> "111"
11변환 -> "1011"

이런식으로 바뀌어 버리니까 js처럼 padstart처럼 해주려고 repeating써주면서 해주려고 했는데, 너무 비효율적일 것 같아서 비트연산을 활용하는 방향으로 틀었다.

let a = 7 // 0111
let b = 11 // 1011

let diff = a ^ b

for i in 0 ..< String(b, radix: 2).count {
    let mask = 1 << i
    if diff & mask != 0 {
        print(i) // 다른 개수만큼 + 1
    }
}

이런식으로 XOR로 서로 다른친구가 있는 비트만 불이 들어오게하고, 그 부분에 불이 들어오는지를 카운팅해주는 것이다 !

---

코드 제출

import Foundation

func solution(_ numbers: [Int64]) -> [Int64] {
    var answer = [Int64]()
    func counting(_ a: Int64, _ b: Int64) -> Int {
        let diff = a ^ b
        var count_diff = 0
        for i in 0 ..< String(b, radix: 2).count {
            let mask = 1 << i
            if diff & Int64(mask) != 0 {
                count_diff += 1
            }
        }
        return count_diff
    }

    for num in numbers {
        var plus: Int64 = 1
        solveLoop: while true {
            if counting(num, num + plus) <= 2 {
                answer.append(num + plus)
                break solveLoop
            }
            plus += 1
        }
    }
    return answer
}

채점 결과

정확성: 72.7
합계: 72.7 / 100.0
잘 맞는지 알았는데 10개중 3개가 틀리다고 나왔다(시간초과)

---

원인 찾기

1. 어처피 아래서부터 1씩 올려주면서 찾는거니까 찾은 것 중에 최소값을 보장될 것이다.
2. 그러면 비트연산을 2가 넘어가려고 할 떄 한번 끊어줄까? 해서 그부분을 수정해보았다.

--

비트연산 2 넘어가면 컷해주기

import Foundation

func solution(_ numbers: [Int64]) -> [Int64] {
    var answer = [Int64]()
    func counting(_ a: Int64, _ b: Int64) -> Bool {
        let diff = a ^ b
        var count_diff = 0
        for i in 0 ..< String(b, radix: 2).count {
            let mask = 1 << i
            if diff & Int64(mask) != 0 {
                if count_diff > 2 { // 두개 넘어가려고 할 때 컷
                    return false
                }
                count_diff += 1
            }
        }
        return count_diff <= 2
    }
    for num in numbers {
        var plus: Int64 = 1
        solveLoop: while true {
            if counting(num, num + plus) {
                answer.append(num + plus)
                break solveLoop
            }
            plus += 1
        }
    }
    return answer
}

채점 결과

정확성: 81.8
합계: 81.8 / 100.0
시간이 대체적으로 빨라지긴했는데 이번엔 2개 틀리게 되었다. (시간초과 동일)

---

2차 수정코드

1. 비트 차이 계산도 nonzeroBitCount로 시간을 많이 단축시켜주고
2. numbers.map을 통해서 append따로 안해주고 바로 return 될 수 있게도 해줬는데, 테스트케이스 10번과 11번은 나를 보내줄 생각이 없어보였다.
3. 전혀 다른 방법으로 풀어야 겠구나 싶었다.

import Foundation

func solution(_ numbers: [Int64]) -> [Int64] {
    func counting(_ a: Int64, _ b: Int64) -> Bool {
        let diff = a ^ b
        let count_diff = diff.nonzeroBitCount
        return count_diff <= 2
    }
    return numbers.map {
        num -> Int64 in
        var plus: Int64 = 1
        solveLoop: while true {
            if counting(num, num + plus) {
                return num + plus
            }
            plus += 1
        }
    }
}

---

결국 답에 항복

import Foundation

func solution(_ numbers: [Int64]) -> [Int64] {
    return numbers.map { num in
        if num % 2 == 0 {
            return num + 1
        }
        else {
            let lastZeroBit = ~num & (num + 1)
            return num + lastZeroBit - (lastZeroBit >> 1)
        }
    }
}

1. 짝수는 이진수 특성상 맨마지막이 0이기 때문에 +1 해주면 비트가 한개 다른 값이 된다 !
2. 중요한 건 홀수 였는데, ~num 부터 이해하는데 좀 오래걸렸다.

어떻게 ~num & (num + 1) 로 가장 멀리있는 0의 위치를 찾아낼 수 있는가 ?

EX) num = '1011' -> ~num = '0100'
num+1 = '1100' , ~num & (num+1) = '0100'

홀수일때 num+1이 가장 오른쪽에 있는 0을 1로 만들고 그 오른쪽은 0으로 만드는 습성이 있어서 num의 보수와 AND 연산을 해버리면, 해당 이진수에서 가장 오른쪽 0 만 1로 만든 친구가 나오게 된다.

정리

1. num + 1 연산은 가장 오른쪽의 0을 1로 바꾸고, 오른쪽의 모든 1을 0으로 바꾼다.
2. ~num은 반전된거라 원래의 num에서 0이었던 위치에 1이 있다.
3. 그래서, ~num과 (num + 1)의 AND연산을 해주면 원래 num에서 0이었던 비트 중
   num + 1에서 1로 바뀐 가장 오른쪽 비트만 1이 된채로 값이 나온다 !

return num + lastZeroBit - (lastZeroBit >> 1)

여기서는 num + lastZeroBit는 결국 1로 꽉찬 친구가 나오는데, 여기에서 lastZeroBit >> 1 을 해주면 가장 오른쪽 0을 1로 채워준 형태가 될 것이다.

예시

1. num = 1011 (11)
2. ~num = 0100 (4)
3. zerobit = ~num & (num+1) => 0100
4. zerobit(0100) + num(1011) => 1111 이렇게 1로 꽉찬형태
5. 1111 - 0010(zerobit>>1) => 1101 = 13
6. 이러면 11을 넣었을 때 답은 13이 나오는 형태다

---

타인의 코드

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

func f(_ number: Int64) -> Int64 {
    return (number | ~number & (number + 1)) & ~((~number & (number + 1)) >> 1)
}

1. ~number & (number + 1) 로 가장 낮은 위치 0 찾는 것 동일하고
2. number | ~number & (number + 1) 가 결국 1로 꽉찬친구를 만들어주는 과정이다
3. ~((~number & (number + 1)) >> 1) 이거도 결국 동일했다. 훨씬 비트스럽에 풀어준 느낌? '1111'이라 그대로 빼주었는데 제 코드는, 그러지 않고 여기서는 정확히 비트연산을 활용했다. 결국에서 0100에서 >>1 해서 0010이 나왔고, 이를 또 보수로 묶어줘서 1101이 나온걸 이제 &연산으로 1111이랑 비교해준거다 결국 그냥 0010을 1111에서 빼준거랑 동일하게 작동하는 것이다.

---