문제 설명

양의 정수 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

문제 예시와 같습니다.

접근 방법

처음에 이 문제에 접근했을 때에는 while문 안에서 현재의 number와 number+i 간의 XOR연산을 사용하여 나온 결과값을 bin()처리하여 1의 갯수가 2개가 되면 정답으로 넣도록 구현하였다. 답은 잘 나왔지만, 입력값이 커질 경우, count()함수가 시간복잡도를 너무나 많이 차지할 것이라는 생각이 들었고, 당연히 시간초과가 발생하였다.

그래서 다른 패턴을 찾아보다가 짝수가 입력될 경우, 이진수로 표현할 때에 가장 뒤에 0이 붙는 다는 것을 알았고, 짝수가 입력된다면 그 수보다 1 큰 수를 정답으로 반환하도록 하면 됐다.

홀수의 경우에는 이진수 표현 문자열에 있는 가장 뒤에 01을 10으로 바꿔주면 됐다. 이진수 표현 문자열이 1로만 되어있을 경우를 대비하여 가장 앞에 0을 붙여주고, 이진수 표현 문자열을 거꾸로 돌려 10이 나오면 01로 바꿔주고 반복을 종료하도록 하였고, int()함수를 사용하여 십진수로 변환한 뒤에 정답으로 반환하도록 하였다.

테스트 7, 8, 9에서 계속 런타임 에러가 발생하였는데 함수 호출 시에 인자 앞에 int를 붙이니 해결되었다. 테스트 케이스 중에 int형이 아닌 입력이 있는 듯 했다..

• 함수 f를 number를 인자로 갖도록 선언한다.
  -> 만약 number가 짝수일 경우, number+1을 반환한다.
  -> 그 외의 경우,
  --> 임시변수 tmp에 bin(number)을 저장한다.
  --> tmp를 tmp[:2]+'0'+tmp[2:]를 통하여 0을 앞에 붙여준다.
  --> tmp를 뒤집는다.
  --> tmp의 길이만큼 반복하는 i에 대한 for문을 돌린다.
  ---> 만약 tmp[i-1]이 1이고, tmp[i]가 0일 경우,
  ----> tmp를 tmp[:i-1]+'01'+tmp[i+1:]로 갱신하고, 반복문을 탈출한다.
  --> tmp1에 tmp를 뒤집은 문자열의 int형을 저장한다.
  --> tmp1을 반환한다.
• 정답을 저장할 리스트 answer를 numbers를 number에 대하여 순회하며 f(int(number))를 호출한 결과로 채운다.
• answer를 반환한다.

solution.py

def solution(numbers):
    def f(number):
        if int(number)%2==0:
            return number+1
        else:
            tmp=bin(number)
            tmp=tmp[:2]+'0'+tmp[2:]
            tmp=tmp[::-1]
            for i in range(1, len(tmp)):
                if tmp[i-1]=='1' and tmp[i]=='0':
                    tmp=tmp[:i-1]+'01'+tmp[i+1:]
                    break
            tmp1=int(tmp[::-1], 2)
            return tmp1
    answer=[f(int(number)) for number in numbers]
    return answer