문제

제한 사항

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

시간 초과 풀이

아이디어

• 원래 수와, 원래 수부터 1씩 증가시킨 수를 XOR 연산한 결과 문자열에 1이 1번 또는 2번 들어가있으면 원래 수와 1 또는 2비트만 다른것이므로, 원래 수부터 1씩 증가시키며 반복문 돌렸다.
• 짧은 코드를 위해 Counter를 사용하였습니다.
• 최대로 인풋이 들어왔다면..
  • 메인 반복문 10만번
  • f(x)에서 while문 한 번 당 Counter 생성시 최대 45의 연산, counter['1']에 대한 접근 2번
  • 여기까지 계산했을 때 900만 번. 즉, while문을 10번만 돌아도 9천만 번, 곧 있으면 1억... 위태위태하네요.

코드

# XOR 연산 => 같으면 0, 다르면 1 => 다른 것의 개수 => 1의 개수를 세어주자
from collections import Counter
def solution(numbers):
    
    def f(x):
        ret = 0
        comp = x + 1
        while True:
            res = format((x ^ comp), 'b')
            counter = Counter(res)
            if counter['1'] == 1 or counter['1'] == 2:
                ret = comp
                break
            else:
                comp += 1
                
        return ret
    
    answer = []
    for n in numbers:
        answer.append(f(n))
    
    return answer

정답 풀이

아이디어

1. 짝수이면, 이진수로 바꿨을 때 xxxxx0으로 끝난다. 그러면, 당연히 해당 짝수보다 크면서 1~2비트 차이나는 정수는 해당 짝수에 1을 더한 수이다. 그러면 가장 마지막 비트가 1로 바뀌면서 1비트 차이 나기 때문이다.
2. 홀수이면, 이진수로 바꿨을 때 xxxxx1로 끝난다. 그러면, 이진수 문자열을 거꾸로 탐색했을 때 처음으로 나오는 0을(인덱스 i일때) 1로 바꿔주고, 인덱스 i+1에 있는 것을 0으로 바꿔준다. 그러면 2비트 차이가 나면서, 원래 수보다 큰 가장 작은 수가 된다.

코드

def solution(numbers):
    def f(x):
        #짝수/홀수 판단
        even = False
        if(x % 2 == 0):
            even = True
        
        #짝수라면 +1 한게 정답
        if even:
            return x+1
        #홀수라면 이진수로 바꿨을 때 가장 끝의 0을 1로, 그 뒤에 수를 0으로 바꾸기
        else:
            binary = format(x, 'b')
            binary = list('0' + binary)
            for i in range(len(binary)-1, -1, -1):
                if binary[i] == '0':
                    binary[i] = '1'
                    binary[i+1] = '0'
                    break
            return int('0b' + "".join(binary), 2)
    
    return [f(n) for n in numbers]

더 깔끔한 코드

• 문자열 함수인 rfind() 함수를 이용해서 더 깔끔하게 짤 수 있다.
• 우리는 짝수든 홀수든 어쨌든 가장 오른쪽의 0을 1로 바꿔줄거니까, 가장 오른쪽의 0의 인덱스를 rfind() 함수를 통해 찾아내서 1로 바꾼다.

  주의) 파이썬에서는 문자열[i] = '1' 과 같이 문자열을 인덱스로 접근해서 값을 바꿀 수 없다.
  무조건 문자열을 list(문자열)로 각 문자마다 따로따로 떼서 리스트로 저장한 다음에 바꿔줘야 한다.
  다시 문자열로 리턴하려면 "".join(리스트)를 해주어야 한다.

• 그리고 나서 원본 수가 홀수이면, rfind()로 찾은 인덱스의 다음 인덱스를 0으로 바꿔준다.

def solution(numbers):
    def f(x):
        binary_str = '0' + format(x, 'b')
        binary = list(binary_str)       
        idx = binary_str.rfind('0')
        
        binary[idx] = '1'
        
        if x % 2:
            binary[idx + 1] = '0'
        
        return int('0b' + "".join(binary), 2)
    
    return [f(n) for n in numbers]