2개 이하로 다른 비트(python, java)

문제 설명

정수 x가 주어졌을 때 x와 비트가 1개에서 2개 정도 다른 수들 중 제일 작은 수를 배열에 넣어서 반환하는 문제이다.

https://school.programmers.co.kr/learn/courses/30/lessons/77885?language=java 

프로그래머스

문제 풀이

첫 번째 접근

처음에는 주어진 숫자를 하나씩 올린 다음 xor 연산자로 서로 다른 숫자를 1로 만들어주고 1의 갯수를 세주면 되겠다고 생각했다. 그러나 이를 위해서는 2차원 반복문이 필요한데 주어진 number의 최대 길이는 100,000이여서 최악의 경우 100,000,000,000번을 계산하게 된다.

 

솔직히 무조건 시간 초과 나겠다고 생각했지만 일단 해보자는 마음으로 코드를 적었고 역시 시간 초과!

두 번째 접근

그럼 시간 초과를 안 내고 어떻게 푸는 건데?

다른 사람들의 풀이를 찾아보니 해답을 얻을 수 있었다.

 

일단 짝수를 보자.

2의 경우에는 이진수가 0000...0010이렇게 되어 있다. 2보다 크면서 서로 다른 이진수 숫자가 2개 이하이며 제일 작은 숫자는 3. 3의 이진수는 0000...0011이다. 

 4라면 0000...00100이고 위의 규칙을 적용하면 000...00101이 답이 된다.

 

즉, 짝수의 경우에는 1을 하나 올려주면 그게 답이 되는 것이다.

 

그렇다면 홀수는 어떻게 풀까?

7의 이진수는 000...0111이다. 그리고 답으로 나온 11의 이진수는 000...1011이다. 맨 마지막으로 나온 0을 1로, 그 다음 비트는 0으로 바꿔줬다.

9의 경우에는 답이 10이고 두 숫자의 이진수를 비교하면 1001과 1010. 즉, 맨 매지막으로 나온 0을 1로 바꿔주고 다음 비트를 0으로 바꿔주는 것을 알 수 있다.

 

그러므로 홀수의 경우 코드를 짤 때 주어진 숫자를 일단 이진수로 바꾼다.

그리고 맨 앞에 0을 하나 붙여준다. 왜냐하면 우리는 맨 마지막 0의 위치를 찾아야 하는데, 모두 1로 이루어진 경우 그 위치가 -1이 나올 수 있기 때문이다.

마지막 0의 위치를 찾았다면 해당 위치와 그 다음 위치를 '10'으로 바꿔준다.

 

참고로 말하자면 파이썬은 이진수로 바뀔때 '0b'가 앞에 붙으므로 앞이 두 글자는 빼고 연산해줘야 한다.

코드

파이썬

def solution(numbers):
    answer = []
    
    for number in numbers:
        if number % 2 ==0:
            answer.append(number+1)
            continue
        
        # 파이썬은 '0b'가 붙어 나와서 앞의 두 글자는 빼고 연산해야 함
        # 이진수로 변환한 값에 계산의 편의를 위해서 '0'을 붙여준다.
        newBin = '0' + bin(number)[2:]
        # 맨 마지막 0 위치를 찾아준다.
        findZero = newBin.rindex('0')
        # 처음부터 맨 마지막 0위치 전 까지의 문자열 + '10' + 바뀐 문자열 뒤에서 부터 마지막까지
        newBin = newBin[:findZero] + '10' + newBin[findZero+2:]
        # 정답에 정수로 변환하여 넣는다.
        answer.append(int(newBin, 2))
                
    return answer

자바

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        
        for(int i=0; i<numbers.length; i++){
            long number = numbers[i];
            if(number % 2 == 0){
                answer[i] = numbers[i]+1;
                continue;
            }
            String binTmp = Long.toBinaryString(number);
            binTmp = '0' + binTmp;
            int zero = binTmp.lastIndexOf("0");
            binTmp = binTmp.substring(0, zero) + "10" + binTmp.substring(zero+2, binTmp.length());
            answer[i] = Long.parseLong(binTmp, 2);

        }
        
        return answer;
    }
}