[Python 파이썬] 프로그래머스 - 2개 이하로 다른 비트

2024년 6월 7일

문제 링크 : 프로그래머스 - 2개 이하로 다른 비트

프로그래머스

 

---

문제 접근

 

주어진 10진수 x와 x보다 큰 모든 수들 중, 2진수로 변환했을 때 비트가 1~2개 다른 수 중 가장 작은 수를 구하는 문제이다.

 

예를 들어, x가 4일 때, 이를 2진수로 바꾸면 100⑵이며, x보다 큰 수는  5, 6, 7 ... 등등 많지만

각각 2진수로 변환하면 101⑵, 110⑵, 111⑵ ... 와 같다.

 

이러한 x보다 큰 수들 중, 2진수로 변환했을 때 x의 2진수 변환 수보다 비트가 2개 이하로 다른 수 중 가장 작은 수를 구하면 되는 문제이다.

 

위에서 예시로 사용한 5, 6, 7 각각 4보다 비트가 1개, 1개, 2개 달라 조건에 충족하지만, 조건에 충족하는 수들 중 가장 작은 수인 5가 정답이 되는 것이다.

 

x를 입력받았을 때 x보다 큰 수를 하나씩 2진수로 변환해 각 자리수를 비교하면 정말 비효율적이고 시간복잡도가 상당할 것이다. x의 최대값이 10^15이기 때문..

10^15를 2진수로 변환하면 자리수가 50개나 되기 때문에, 그리고 조건에 맞는 수를 찾기까지 많은 연산을 하게 될 수도 있기에 규칙을 찾아서 효율적으로 접근해야 한다.

 

x가 짝수

 

 

x가 짝수라면 조건에 맞는 수는 간단하게 찾을 수 있다.

2^0 자리수의 값이 0이기 때문에, 해당 자리수 값을 1로 바꾼 수, 즉 x + 1이 조건에 맞는 수이다.

 

x가 홀수

 

 

x가 홀수라면 말이 달라진다. 여기서 우리는 규칙을 추가로 찾아야 한다.

위의 예시를 보면, 오른쪽에서부터 왼쪽 순서대로 탐색했을 때 가장 먼저 나온 0을 1로 바꾸고, 해당 자리수 바로 오른쪽의 수를 0으로 바꾸는 것이 x보다 큰 수이면서 2비트만 다르다는 조건을 충족하고, 그러한 수 중 가장 작은 수이다.

 

만약 11111⑵과 같이 모든 비트가 1인 경우는 어떻게 해야 할까?

 

 

이는 맨 앞 자릿수에 0을 더 추가해주어야 한다. 31보다 큰 32, 33, 34,... 모두 자리 수가 한 단계 커지기 때문.

011111⑵ 로 변환시켜주고, 앞에서의 로직과 똑같이 수행시켜주면 된다.

---

순서도

 

1. x가 짝수/홀수일 때 로직을 구분한다.

2. x가 짝수라면, x + 1을 answer에 append한다.

3. x가 홀수라면 다음과 같이 로직을 수행한다.
3-1. numbers의 각 요소 x에 대해 2진법으로 변환한다. 11111⑵와 같이 모든 자리수가 1일 경우를 대비해 가장 큰 자리수 앞에 0을 추가한다.
3-2. 자리수가 가장 작은 끝부터 큰 끝까지 탐색을 진행하여 처음 0이 나온 자리수의 값을 1로 치환하고, 바로 아래 자리수 값을 0으로 치환한다.
3-3. 해당 2진수를 10진수로 변환 후 answer에 append한다.

4. answer을 return한다.

 

 

---

전체 코드

 

def binary_bit(num):
    # 31(11111)같은 모든 자리수가 1인 경우 대비, 한 자리수 더 크게 사이즈 잡기
    result = [0]
    length = 1
    stack = []
    while num > 0:
        stack.append(num % 2)
        num //= 2
        length += 1
    
    while stack:
        result.append(stack.pop())

    return result, length

def solution(numbers):
    answer = []

    for idx in range(len(numbers)):
        now = numbers[idx]
        
        # 현재 수가 짝수 -> 2^0 자리수를 0에서 1로 치환
        if now % 2 == 0:
            answer.append(now + 1)
        # 현재 수가 홀수 -> 가장 자리수가 작은 0을 1로 치환, 해당 자리수 기준 오른쪽 1을 0으로 치환
        else:
            now_binary, now_length = binary_bit(now)
            for idx in range(now_length - 1, -1, -1):
                if now_binary[idx] == 0:
                    now_binary[idx] = 1
                    now_binary[idx + 1] = 0
                    break
            next = 0
            for i in range(now_length):
                next += (now_binary[i] * 2**(now_length - i - 1))
            answer.append(next)
        

    return answer

if __name__ == "__main__":
    numbers = [2, 7]
    print(solution(numbers))

---

풀이 후기

 

단순하게 접근하면 안되고, 홀짝 규칙을 찾아 솔루션을 제시해야 하는 문제였다.