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

월간 코드 챌린지 시즌 2 문제입니다.

---

문제 설명

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

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

예를 들어,

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

  

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

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

 

제한사항

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

 

입출력 예

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

---

나의 풀이

def solution(numbers):
    answer = []
    
    for number in numbers:
        if number%2 == 0: # number가 짝수이면 1을 더하면 끝
            answer.append(number + 1)
            continue
        n = bin(number)[2:][::-1] + '0' # 2진수 역순으로 표현
        zero = n.find('0') # 최초 0의 index
        n = (n[:zero-1]+'01'+n[zero+1:])[::-1] # 1 0 -> 0 1 바꾼 후 다시 역순으로 돌림
        answer.append(int(n, 2)) # 10진수로 변경 후 list에 추가
        
    return answer

 

우선 이 문제는 다음 문제와 상당히 유사하다. 참고하면 도움이 될 것이다.

2021.08.14 - [프로그래머스 lv2] 다음 큰 숫자 (효율성 높은 풀이)

[프로그래머스 lv2] 다음 큰 숫자 (효율성 높은 풀이)

 

숫자가 짝수인 경우

1만 더해주면 된다.

우선 짝수를 2진수로 나타내면 1의 자리는 항상 0이다. 그래서 숫자가 짝수일 경우엔 그냥 1만 더해주면 된다.

 

숫자가 홀수인 경우 다음과 같이 처리하면 된다.

가장 오른쪽에 있는 '0'

우선 오른쪽부터 탐색하여 가장 먼저 나오는 0을 찾는다.

오른쪽의 1과 맞바꾼다.

그럼 2개의 비트가 다르게 되고, 그 중 가장 작은 수가 된다. 끝!

 

코드로 구현

2021.08.14 - [프로그래머스 lv2] 다음 큰 숫자 (효율성 높은 풀이)

[프로그래머스 lv2] 다음 큰 숫자 (효율성 높은 풀이)

이 문제에서와 마찬가지로 편의를 위해 역순으로 문제를 풀이한다.

2진수 및 역순으로 표현

역순으로 표현

위에서 예시를 들었던 1 0 1 0 1 1 1 을 역순으로 표현하면 1 1 1 0 1 0 1 이 된다.

뒤에 '0' 추가

그리고 0을 찾아야 하는데 0이 없는 경우를 대비해 맨 뒤에 0을 붙여준다. (역순이기 때문에 실제론 맨 앞에 0을 붙이는 것과 동일하다)

n = bin(number)[2:][::-1] + '0' # 2진수 역순으로 표현

코드로 나타내면 위와 같다. bin으로 10진수를 2진수로 바꿀 수 있지만 바꾸게 되면 2진수의 경우 맨 앞에 '0x'가 붙는 문자열이 된다. 0x를 떼어내기 위해 [2: ]로 슬라이싱 한 후 [ : :-1]로 역순으로 바꾼다. 그리고 + '0' 으로 뒤에 '0'을 붙인다.

'0' 찾기

최초로 등장하는 '0'을 찾는다

왼쪽부터 탐색해 최초로 등장하는 '0'의 위치를 찾는다.

당연한 얘기지만 '0'이 없는 경우는 없다. 왜냐하면 위에서 임의로 '0'을 붙여줬기 때문.

zero = n.find('0') # 최초 0의 index

 

'1, 0' 맞바꾸기

회색으로 칠해진 부분은 바뀌지 않을 부분이다.

회색으로 칠해진 부분을 바뀌지 않을 부분이다.

노란색으로 칠해진 0의 위치는 zero라는 변수에 담겨있다.

그렇다면 왼쪽의 회색 부분은 n[ :zero-1] 로 슬라이싱 할 수 있다.

그리고 초록, 노란색으로 칠해진 '10' 부분은 '01' 로 바뀐다.

나머지 오른쪽 회색 부분은 n[zero+1: ] 로 슬라이싱 할 수 있다.

그리고 원래 숫자로 바꾸기 위해서 다시 역순으로 뒤집는 과정도 필요하다.

변경 후 역순으로 뒤집은 결과

n = (n[:zero-1]+'01'+n[zero+1:])[::-1] # 1 0 -> 0 1 바꾼 후 다시 역순으로 돌림

 

리스트에 추가

마지막으로 위의 과정들로 변경된 n을 10진수로 바꿔 answer 리스트에 추가하면 된다.

answer.append(int(n, 2)) # 10진수로 변경 후 list에 추가

return

return answer

 

테스트 결과

문제의 제한 사항에서

각 숫자의 최대 크기가 1,000,000,000,000,000 이고, 최대 100,000 개의 숫자가 있을 수 있기 때문에 일반적으로 반복문으로 풀이하면 무조건 시간 초과로 실패할 것이다.

나름 문자열로 효율성 있게 풀었다고 생각했는데 몇몇 테스트에서 꽤 많은 시간이 소요되었다.