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

[문제 보기]

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

• x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

예를 들어,

• f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

수비트다른 비트의 개수

2	000...0010
3	000...0011	1

• f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

수비트다른 비트의 개수

7	000...0111
8	000...1000	4
9	000...1001	3
10	000...1010	3
11	000...1011	2

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 1015

---

입출력 예

numbers, result

[2,7]

[3,11]

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

 

https://programmers.co.kr/learn/courses/30/lessons/77885

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

 

---

문제 풀이

 

1. 전부다 비교하면서 구하는 방법(시간초과)

처음에 구현한 코드에서는 nonzerobitCount를 이용해서 하나씩 비교하는 방식으로 구현했는데 시간초과가 떠서 다른 방법을 찾았다.

 

Int > Instance Property

nonzeroBitCount

The number of bits equal to 1 in this value’s binary representation.

var nonzeroBitCount: Int { get }​

let x: Int8 = 0b0001_1111
// x == 31
// x.nonzeroBitCount == 5​

// 처음에 제출한 코드 (시간초과)
func solution(_ numbers:[Int64]) -> [Int64] {
    
    return numbers.map {
        var ans = $0 + 1
        for i in (ans...) {
            if case (1...2) = (i^$0).nonzeroBitCount {
                ans = i
                break
            }
        }
        return ans
    }
}

처음에 제출한 코드

 

 

2. 비트연산자로 구하는 방법(최종버전)

 

만약 비교해야할 수가 짝수라면 2진법으로 나타냈을 때 마지막 끝자리 숫자가 0인 특징을 가지고 있으므로 이걸 1로 바꾸는게 (원래 수에서 1을 더함) 가장 작은 그 다음 수이다.

만약에 주어진 수가 홀수라면..

이진수로 나타냈을 때 가장 작은 (가장 끝자리에 있는) 0을 1로 바꾸고 (여기서 1번 바꿈), 0보다 더 끝자리에 있는 1을 0으로 바꾸는게 (여기서 2번째로 바꿈) 가장 작은 그 다음 수이다.

 

예를들어 설명하면

숫자 10 = 1010(2)이라면 오른쪽 마지막 끝자리가 0을 1로 바꾸는것이 가장 작은 다음수가 된다.

짝수라면 이렇게 1개만 바꾸는 경우가 된다는 것이다.

 

숫자 11 = 1011(2)이라면 그 다음수를 구하려면 우선 가장 작은 0을 1로 바꾸는걸 고려해볼수있다. 

1111(2) 그렇지만 문제 조건에서 최대 2개까지 바꾸는게 가능하므로 그 다음수중에서 최대한 숫자를 작게 만들기위해 방금 바꾼 0의 오른쪽에 있는 1을 0으로 바꿔서 숫자를 작게 만들어야 한다.

그래서 1111(2) -> 1101(2) = 13이 최종적으로 답이 된다.

 

구현에서는, 가장 작은 0을 찾기 위해서 다음과 같은 연산을 거친다

원래수 11 = 1011(2)

11 + 1 = 1111(2)

~1011 = 0100(2)

위 두수를 and연산하면 0100이 되고, 1이 위치한 곳이 0이 있던 자리이다.

방금 가장작은 0을 구한것이므로 0의 오른쪽에는 항상 1이 있다.

shift연산을 통해 1의 위치도 구할 수 있다.

100(2) >> 1 = 10(2)

지금까지 구한 값들을 이용해서 최종답을 구하기위해 다음과 같은 연산을 거친다.

0100 | 1011 = 1111 -> a,

~10 = 1101 -> b,

a & b = 1111 & 1101 = 1101 = 13

 

// 최종코드
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)
        }
    }
}

---

생각 정리

비트연산자 관련

 

1. not: ~

~1110 => 0001

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

 

2. or: |

1100 | 1001 => 1101

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

 

6 비트연산 관련 트릭 설명글

https://shoark7.github.io/programming/knowledge/some-useful-bit-tricks-and-usages

현실에서 유용한 Bitwise 연산 및 활용 모음