문제

link

나의 풀이

def solution(numbers):
    answer = []
    limit = 10**15
    for number in numbers:
        target = number
        while target <= limit:
            diff = bin(number ^ target)
            cnt = diff.count('1')
            if cnt == 1 or cnt == 2:
                answer.append(target)
                break
            target += 1
    return answer

이 코드는 시간 초과가 발생하였다.

그래서 내가 정리한 최적화 방법 중 하나인 수학적인 공식을 이용하여 시간 복잡도를 줄여야 한다. 사실 그래서 케이스별로 수열적인 관점에서 패턴을 찾아내려고 했지만 실패하였다. 계속 시간을 투자했던 이유는 안타깝게도 패턴이 보일 듯 말 듯 했기 때문이다.. 그래서 엄청난 삽질 끝에 포기하였다.

실패한 이유를 고찰해보자면, 다루는 수가 '비트'인데 비트를 문제 해결 관점에서 크게 비중을 주지 못한 것 같다. 그래서 GPT에세 문제 풀이를 요청하여 얻은 코드는 다음과 같다.

def solution(numbers):
    result = []
    for number in numbers:
        # 짝수인 경우
        if number % 2 == 0:
            result.append(number + 1)
        else:
            # 홀수인 경우
            # 가장 오른쪽의 0을 1로 변경하고, 그 직전의 1을 0으로 변경
            bit_mask = 1
            while number & bit_mask:
                bit_mask <<= 1
            result.append(number + bit_mask - (bit_mask >> 1))
    return result

이 문제 풀이 원리는 그리디였다. 비트를 짝수와 홀수 관점을 사용하여 그룹을 구분한다. 그러면 패턴을 찾기 쉬워진다. 짝수는 단순하게 +1을 한 것이 정답이 된다. 그리고 홀수는 가장 오른쪽의 0을 1로 변경, 그 직전의 1을 0으로 변경하는 것이 법칙이다. 이 법칙이야 말로 패턴을 찾아야 한다는 나의 규칙에 부합한 것이었는데, 내가 짝수와 홀수로 그룹을 구분지어서 판단하지 못한 것이 패착이다.

고찰

1. 패턴이 쉽게 보이지 않는다면, 포기해야 한다.
2. 문제에서 제시한 수 체계는 비트이며, 최대 2개의 비트가 달라야 한다는 조건을 통해 매우 '비트'스럽게 문제 해결이 될 것이란 것을 알아야 했다. (비트 연산자를 사용한다던지, 혹은 비트로 변환한 수를 통해 패턴을 찾는다던지)