2개 이하로 다른 비트

[문제 Link] https://programmers.co.kr/learn/courses/30/lessons/77885

문제 설명

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

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

예를 들어,

f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

수	비트	다른 비트의 개수
2	000…0010
3	000…0011	1

f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

수	비트	다른 비트의 개수
7	000…0111
8	000…1000	4
9	000…1001	3
10	000…1010	3
11	000…1011	2

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

제한사항

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

입출력 예

numbers	result
[2,7]	[3,11]

입출력 예 설명

로직

먼저 숫자들의 규칙을 찾아야한다. 예를 들면 짝수의 경우 이진수로 바꾸었을 때 마지막 숫자는 0이 되므로 바로 다음 숫자를 결과로 보내면 된다.

아래의 표를 확인하면,

숫자	비트	결과값	결과 비트
0	00000	1	00001
1	00001	2	00010
2	00010	3	00011
3	00011	5	00101
4	00100	5	00101
5	00101	6	00110
6	00110	7	00111
7	00111	11	01011
8	01000	9	01001
9	01001	10	01010
10	01010	11	01011
11	01011	13	01101
12	01100	13	01101
13	01101	14	01110
14	01110	15	01111
15	01111	23	10111
16	10000	17	10001
17	10001	18	10010
18	10010	18	10010
19	10011	21	10101
20	10100	21	10101

짝수는 모두 다음 수를 결과값으로 가진다.
2의 제곱수 보다 1작은 수(2^n-1)는 모두 결과값으로 2^n-1 + 2^(n-1)이다.
나머지 수들은 1의 자리 숫자부터 0의 위치에 따라 달라진다.

전체 코드

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Solution
{
    public static long[] solution(long[] numbers)
    {
        long[] answer = new long[numbers.Length] ;
        for (int i = 0; i < numbers.Length; i++)
        {
            string num = Bi((long)numbers[i]);
            if(numbers[i]%2==0) // 짝수일 경우
                answer[i] = (long)(numbers[i] +1); 
            else if(!num.Contains('0')) //2^n-1인 경우
            {
                answer[i] = (long)(numbers[i] + (numbers[i]+1)/2);
            }
            else //나머지 경우
            {
                for(int j =num.Length-1;j>=0;j++) //첫번째 0을 찾는다.
                {
                    if(num[j]=='0')
                    { 
                        answer[i] = numbers[i] + (long)Math.Pow(2,(num.Length-j-1)-1);
                        break;
                    }
                }
            }
        }

        return answer;
    }
    public static string Bi(long num)
    {
        return Convert.ToString(num,2);
    }


    public static void Main(string[] args)
    {
        long[] numbers = new long[] {2,7};
        long[] results = solution(numbers);
        foreach(var result in results)
            Console.WriteLine(result);
    }
}