프로그래머스 Lv. 2 Swift 알고리즘 - 2개 이하로 다른 비트

bit에 대한 이해... 알고리즘에 대한 이해가 필요하다는 생각을 하게 만들어준 문제다.

나름 열심히 규칙을 찾아서 문제를 풀었는데 1차, 2차 모두 시간 초과 문제가 발생했다.

나름 1차에 비해 2차때는 속도를 많이 줄였다고 생각했는데도 풀리지가 않았다...

 

그래서 구글링을 좀 해보니 nonzerobitCount와 비트연산자 두 가지 이야기들이 많이 나왔다.

nonzeroBitCount라는게 있는줄도 몰랐는데... 애플공식홈페이지를 참고해보니...

2진법으로 표현했을 때 비트가 1과 같은 숫자...? 라고 해석할 수 있다.

솔직히 무슨 소린지 모르겠지만 Discussion을 보니 좀 이해가 간다 31이라는 10진수를 2진수로 바꾸었을때 나오는 1의 개수!

내가 문제를 풀면서 직접 구했던 것인데 여기선 이렇게 편하게 메소드가 존재했었다!

 

그런데 이를 이용하고도 시간초과가 난 사례들을 보아 비트연산자의 더 깊숙한 이해를 해야 문제를 풀 수 있을 것 같았다.

그래서 참고한 블로그는 이 곳이다.

 

https://turume.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-2%EA%B0%9C-%EC%9D%B4%ED%95%98%EB%A1%9C-%EB%8B%A4%EB%A5%B8-%EB%B9%84%ED%8A%B8-Swift

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

 

 

 

 

 

이 문제를 풀면서 생각한 논리적 흐름

1. numbers에 4를 나눈 나머지에 3을 뺐을 때 0이 아니면 그 숫자의 위치에서 +1만 해줘도 값이 나온다.
2. 따라서 위의 과정에서 0이 되는 경우, 각 값들을 2진법으로 바꿔서 1의 개수를 세준다.
3. 1의 개수가 numbers원소와 같은 경우, 그러면서 가장 낮은 값을 찾기위해 while문을 돌린다.
4. 0이 되는 경우에 2의 지수로 값을 더해준 경우가 가장 낮은 값이기 때문에
5. byTwo를 이용해 순차적으로 비교해준다.

 

 

* 효율성 틀린 코드

import Foundation

func solution(_ numbers:[Int64]) -> [Int64] {
    var ans: [Int64] = []
    
    for j in 0..<numbers.count {
        if numbers[j] % 4 - 3 == 0 {
            let count = String(numbers[j], radix: 2).filter {($0) == "1"}.count
            for i in (numbers[j] + 1)... {
                if count == String(i, radix: 2).filter({($0) == "1"}).count {
                    ans.append(i)
                    break
                }
            }
        } else {
            ans.append(numbers[j]+1)
        }
    }
    
    return ans
}

 

* 2차 시도한 코드

import Foundation

func solution(_ numbers:[Int64]) -> [Int64] {
    var ans: [Int64] = []

    for j in 0..<numbers.count {
        var byTwo: Int64 = 2
        
        if numbers[j] % 4 - 3 == 0 {
            let count = String(numbers[j], radix: 2).filter({($0) == "1"}).count
            
            while true {
                if count == String(numbers[j] + byTwo, radix: 2).filter({($0) == "1"}).count {
                    ans.append(numbers[j] + byTwo)
                    break
                }
                byTwo *= 2
            }
            
        } else {
            ans.append(numbers[j]+1)
        }
    }
    return ans
}

 

 

*참고한 코드

import Foundation

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

 

정리(Today I Learned)

 

비트 연산자를 알고 있으면 나중에 2진법 알고리즘과 관련하여 크게 도움을 받을 수 있을 것 같아 정리

< 비트연산자 >

1. not: ~

~1101 => 0010

let initialBits: UInt8 = 0b00001111
let invertedBits = ~initialBits  // equals 11110000

 

2. or: |

1110 | 1001 => 1111

let someBits: UInt8 = 0b10110010
let moreBits: UInt8 = 0b01011110
let combinedbits = someBits | moreBits  // equals 11111110

 

3. and: &

1100 & 1111 => 1100

let firstSixBits: UInt8 = 0b11111100
let lastSixBits: UInt8  = 0b00111111
let middleFourBits = firstSixBits & lastSixBits  // equals 00111100

 

4. shift: >>, <<

100>>1 => 010

100<<1 => 1000

let shiftBits: UInt8 = 4   // 00000100 in binary
shiftBits << 1             // 00001000
shiftBits << 2             // 00010000
shiftBits << 5             // 10000000
shiftBits << 6             // 00000000
shiftBits >> 2             // 00000001

 

5. xor: ^

1101 ^ 1011 => 1001

let firstBits: UInt8 = 0b00010100
let otherBits: UInt8 = 0b00000101
let outputBits = firstBits ^ otherBits  // equals 00010001