2개 이하로 다른 비트

📍 2개 이하로 다른 비트

💡 문제

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

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

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

⚠️ 제한사항

1 ≤ numbers의 길이 ≤ 100,000
0 ≤ numbers의 모든 수 ≤ $1^{15}$

✅ 풀이

👆 첫 번째 풀이 (성공)

2진수는 0과 1로만 구성되어 있기 때문에 규칙만 찾는다면 어렵지 않게 풀 수 있었다. 내가 찾은 규칙은 다음과 같다.

숫자가 짝수라면,
- 가장 마지막 자리 수는 항상 0이다.
- ex. 1010, 1110, ...
- 가장 마지막 자리 수를 1로 변경하면 답이다.
- ex. 10 → 11, 111010010 → 111010010
숫자가 홀수라면,
- 가장 마지막 자리 수는 항상 1이다.
- 값이 0인 자리를 1로 바꾸게 되면 그 오른쪽 자리는 0이 된다. (올림)
- 가장 작은 수를 찾아야 하기 때문에 가장 오른쪽에 있는 0을 기준으로 비트를 변경하면 답이다.

class Solution {
    fun solution(numbers: LongArray): LongArray {
        var answer: LongArray = longArrayOf()
        val s = Stack<Int>()
 
        numbers.map { 
            // 짝수: 가장 마지막 자리 수를 1로 변경 (10 -> 11)
            // 홀수: 1. 가장 마지막 "0"의 자리 수를 1로 변경 (01 -> 11)
            //       2. 구한 "0"의 자리수 다음 자리를 0으로 변경 (11 -> 10)
            val s = StringBuilder("0" + it.toString(2))
 
            if (it % 2 == 0L) {
                s.setCharAt(s.length - 1, '1')
            } else {
                val idx = s.lastIndexOf("0")
 
                s.setCharAt(idx, '1')
                s.setCharAt(idx + 1, '0')
            }
 
            answer += s.toString().toLong(2)
        }
 
        return answer
    }
}

🔥 다른 사람의 풀이 1

비트 연산이라는 것이 존재한다. 그렇지만 나는 비트 연산을 무서워한다. 뭐 오른쪽으로 한 칸씩 옮기면 값이 1/2배가 되고, 왼쪽으로 한 칸씩 옮기면 2배가 되고 어쩌구 저쩌구는 머리에 잘 들어오지 않는다. 그래서 비트 연산 없이 이 문제를 풀었었는데...

세상에나 역시나 비트 연산을 사용한 풀이가 제일 위에 있었다. 생각해보니 비트 연산을 모르니까 코틀린의 비트연산자나 함수도 제대로 알아보지 않았던 것 같아 이번 기회에 간단히 알아보았다.

inv(): 모든 비트 반전 (지정되지 않은 상위 비트는 0으로 채워진다.)
shr (shift right): 부호 비트를 제외한 모든 비트를 오른쪽으로 밀어준다.
- 왼쪽으로 밀어주는 shl (shift left)도 있음
and: and 연산을 한다. (비트가 둘 다 1이면 1, 아니면 0)
- 보통 비트를 0으로 만들 때 사용한다. - clear
- 추가로, 비트를 확인할 수도 있다. (원하는 위치에 1을 넣어보면 비트를 알 수 있다.)
or: or 연산을 한다. (비트가 하나라도 1이면 1, 아니면 0)
- 보통 비트 값을 1로 설정하고 싶을 때 사용한다. - set
xor: xor 연산을 한다. (비트가 다르면 1, 같으면 0)
- 보통 비트별로 동일한지 확인하기 위해 사용한다.

알아본 내용을 토대로 코드를 해석해보자면..

n을 반전시킨 수와 n을 and 연산한다.
- n의 자릿수 길이의 0으로만 구성된 수가 나온다.
그 수에, 1을 더한다. → it
- 000...1 형태가 된다.
n과 it를 or 연산한다. → o
- n의 가장 오른쪽 비트를 1로 만들어준다.
it를 오른쪽으로 한칸 밀어주고, 반전시킨다. → p
- n의 자릿수 길이의 1로만 구성된 수가 나온다.
o와 p를 and 연산한다.
- 모두 1인 비트만 1이 된다.

정말 해석만 했다. 뭔가뭔가 원리는 내 풀이랑 비슷한것도 같은데 제대로 된 이해는 못하겠다.

class Solution {
    fun solution(numbers: LongArray): LongArray {
        return numbers.map { num -> (num.inv() and num + 1).let { num or it and (it shr 1).inv() } }.toLongArray()
    }
}

🤯 다른 사람의 풀이 2

나는 String 타입은 특정 범위만 어떤 문자열로 변경하지 못하는 줄 알아서 StringBuilder를 사용했는데, 아니 글쎄 replaceRange()라는 함수가 있는 것이다!

✨ replaceRange(startIndex: Int, endIndex: Int, replacement: CharSequence)

startIndex ~ endIndex-1 까지의 문자열을 replacement로 바꿔준다.
startIndex, endIndex 대신 IntRange 형태를 넣어줄 수도 있다!

홀리몰리.. 오늘도 또 알아간다.

class Solution {
    fun solution(numbers: LongArray): LongArray {
        return numbers.map {
            val str = it.toString(2)
            if (!str.contains('0')) ("10" + str.drop(1)).toLong(2)
            else {
                val last = str.lastIndexOf('0')
                if (last == str.lastIndex) str.replaceRange(last..last, "1").toLong(2)
                else str.replaceRange(last..last + 1, "10").toLong(2)
            }
        }.toLongArray()
    }
}

💭 후기

비트 연산은.. 화이팅 해보는거고, replaceRange는 정말 많이 사용할 것 같다!