[프로그래머스] 2개 이하로 다른 비트,월간 코드 챌린지 시즌2, python, C

https://programmers.co.kr/learn/courses/30/lessons/77885

코딩테스트 연습 - 2개 이하로 다른 비트

def solution(numbers):
    answer = [0] * len(numbers)
    for i in range(len(numbers)):
        tmp = 1    
        while numbers[i] & tmp:
            tmp <<= 1
        answer[i] = numbers[i] + tmp - (tmp>>1)
    return answer

월간 코드 챌린지 시즌 2를 참여했을땐 어떻게 풀어야하는지 잘 몰랐는데

다시 시간 잡고 푸니까 쉽게 풀렸다.

문제를 풀때 여러 단계로 규칙을 찾으려 노력했는데, 하위 두비트가 00,01,10 일경우 1을 더하면 되고 11인 경우 새로운 규칙을 찾는 것을 먼저 확인했다.

최하위 비트가 11 인경우 1이 있는 최상위 비트와 하나 위에 있는 비트를 토글하면  될것같았다.

예를 들면 7 = 2b111인데 최상위 비트는 2^2 자리가 되고 하나 위에있는 비트는 2^3이 된다.

각 자리를 토글하게 되면 2b1011 = 11 이 되어서 f(7) = 11을 만족한다.

하지만 이렇게 만들면 만족하지 못하는 수가 있어서 실패하게 된다. 

 

최상위 비트와 하나 위 비트를 토글하는 것을 응용하면 되지 않을까 생각이 들어서 이리저리 생각을 했다.

그러다 제일 아래에서부터 찾아올라가면서 1이 아닌 비트를 찾고, 해당 비트(0)와 하나 아래 비트(1)를 토글하면 되지않을까 생각이 들었다.

그대로 구현했더니 성공!

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

// numbers_len은 배열 numbers의 길이입니다.
long long* solution(long long numbers[], size_t numbers_len) {
    // return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요.
    long long* answer = (long long*)malloc(numbers_len*sizeof(long long));
    long long tmp;
    int i;
    
    for (i = 0; i< numbers_len; i++)
    {
        tmp = 1;
        while (numbers[i] & tmp)
            tmp <<= 1;
        answer[i] = numbers[i] + tmp - (tmp >> 1);
    }
    return answer;
}

C는 tmp 값이 int값을 넘어버릴수 있으니 long long으로 선언해야한다.