[4코1파] #83. LV 2. 2개 이하로 다른 비트

gunny·2023년 3월 27일

4코1파 코딩테스트 코딩테스트 python 프로그래머스 2개 이하로 다른 비트 프로그래머스 2개 이하로 다른 비트 python

코딩테스트

목록 보기

83/530

[4코1파] 4명의 안드로이드 개발자와 1명의 파이썬 개발자의 코딩 테스트 서막 : 4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원

START :

[3코1파] 2023.01.04~ (83일차)
[4코1파] 2023.01.13~ (74일차)

Today :

2023.03.27 [83일차]

프로그래머스 LV 2
2개 이하로 다른 비트
https://school.programmers.co.kr/learn/courses/30/lessons/77885

문제 설명

양의 정수 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
문제 예시와 같습니다.

문제 풀이 방법

10**15까지의 제한이 있긴했지만
num에서 +1을 더해가면서, 비트 연산을 하고 비트연산된 값에서
1의 count를 센다음 1이상 2이하이면 return 하도록 로직을 짜보았지만

테스트 10, 11에서 시간초과 실패

양의 정수 x의 값이 10**15까지 가기 때문에 이걸 연산하면서 시간이 오래 걸림..

이건 다른 로직이 있을 수 밖에 없어서 살펴보니
짝수와 홀수에 따라서 다른 비트를 찾는 과정은 아래의 규칙을 가지고 있었음

(1) 짝수일 때 비트가 무조건 0이기 때문에 +1 한 값이 비트가 1개가 차이나면서 가장 작은 숫자가 차이가 날 것임!
(2) 홀 수 일때는 끝에서부터 0을 찾고, 0을 1로 바꿔주면 비트차이가 2개 이하인 숫자가 됨
이 값이 가장 작은 수가 될 수 없으므로, 0을 1로 바꾼 후에 비트 자리 다음을 0으로 만들면 가장 작은 수가 됨!

내 코드

def solution(numbers):
    answer = []
    
    for num in numbers:
        if num%2==0:
            answer.append(num+1)
        else:
            tmp_num = '0' + bin(num)[2:]
            idx = tmp_num.rfind('0')
            tmp_num = list(tmp_num)
            tmp_num[idx], tmp_num[idx+1] = '1', '0'
            answer.append(int(''.join(tmp_num),2))
    
    return answer

증빙