[알고리즘] Programmers 2개 이하로 다른 비트 #Python

김상현·2022년 9월 27일
0

알고리즘

목록 보기
197/301
post-thumbnail

[Programmers] 2개 이하로 다른 비트 바로가기

📍 문제 설명

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

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

예를 들어,

  • f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.
비트다른 비트의 개수
2000...0010
3000...00111
  • f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.
비트다른 비트의 개수
7000...0111
8000...10004
9000...10013
10000...10103
11000...10112

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


📍 제한 사항

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

📍 입출력 예

numbersresult
[2,7][3,11]

📍 문제 풀이

📌 처음 접근한 방법

  • 짝수의 경우 20 의 자리 즉 1의 값을 나타내는 비트의 자리가 항상 0 이므로 이 값을 1로 바꾸면 x 보다 크고 x와 비트가 1개 다른 조건에 해당하므로 짝수 + 1 의 값을 반환한다.
  • 홀수의 경우 주어진 숫자 numbernumber 보다 큰 모든 수를 xor 로 비교하며 비트의 불일치 정도가 2 이하인 값을 반환하는 방법을 수행했다.
  • 위 방식은 홀수의 경우에서 너무 많은 반복문을 수행하기 때문에 시간초과가 발생한다.

✍ 코드

def solution(numbers):
    answer = []
    for number in numbers:
        if number % 2 == 0:
            answer.append(number+1)
            continue
        num = number
        while True:
            num += 1
            if bin(number^num).count('1') < 3:
                answer.append(num)
                break
    return answer

📌 새롭게 접근한 방법

  • 짝수의 경우는 위와 같고, 홀수의 경우에서 다른 방식을 적용하였다.
    • number 의 값을 2진수로 변환한 후 앞에 '0' 을 추가한다.
    • 변환한 값의 맨 마지막 인덱스(i) 바로 전부터 검사하여 현재 number 의 인덱스의 값이 '0' 일 경우,
      • 현재 인덱스(i) 위치의 값은 '1' 로 바꾸고 그 다음 인덱스 값(i+1)은 '0' 으로 바꾸어 x 보다 크고 x와 비트가 2개 다른 조건에 맞추는 가장 작은 값을 반환한다.

✍ 코드

def solution(numbers):
    answer = []
    for number in numbers:
        if number % 2 == 0:
            answer.append(number+1)
        else:
            number = ['0'] + list(format(number,'b'))
            for i in range(len(number)-2,-1,-1):
                if number[i] == '0':
                    number[i], number[i+1] = '1', '0'
                    answer.append(int(''.join(number),2))
                    break
    return answer
profile
목적 있는 글쓰기

0개의 댓글