[C#]프로그래머스 - 2개이하로다른비트

문제 설명

양의 정수 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

 

내 풀이(1차) 

using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.Length];
        List<char> sen = new List<char>();
        List<char> sen2 = new List<char>();
        for(int i=0; i<numbers.Length; i++)
        {
            long temp =numbers[i];
            string n_string = Convert.ToString(numbers[i], 2);
            sen= n_string.ToList();
            while(true)
            {
                temp++;
                string n_string2 = Convert.ToString(temp, 2);
                sen2 = n_string2.ToList();
                if(sen.Count != sen2.Count)
                {
                    sen.Insert(0,'0');
                }
                int one=0;
                for (int j =0; j<sen2.Count; j++)
                {
                    if (sen[j] != sen2[j])
                    {
                        one++;
                    }
                    if(one>2) 
                    {
                        break;
                    }
                }
                if(one<=2)
                {
                    answer[i]+=temp;
                    break;
                }
            }
        }
        return answer;
    }
}

설명 : 우선 초기에는 배열의 숫자를 2진수 비트값으로 변환한 후 1씩더해가며 비트가 2개이상 다른지를 판별하는 반복문으로 풀어보았다.

그 결과 문제의 제한사항에서 막혀 런타임 에러에 막혔다. 때문에 1씩 더하며 비트 값을 비교하는 것이 아닌 규칙을 찾아보기로 하였다.

 

찾은 규칙

1.  2진수 비트 값으로 변환된 배열의 숫자의 끝값과 끝값의 전값에 '0'이 존재한다면 숫자의 +1을 한 값을 리턴

2.  2진수 비트 값으로 변환된 배열의 숫자의 끝값과 끝값의 전값이 모두 '1'이라면 '0'이 나올때까지 탐색

3.  '0'이 나온 시점에서 '0'을 '1'로 변환하고 그 다음값을 '0'으로 변환 

ex) '110111' => '111011'

 

 

내 풀이(2차)

using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.Length];
        List<char> sen = new List<char>();
        for(long i=0; i<numbers.Length; i++)
        {
            string n_string = Convert.ToString(numbers[i], 2);
            sen= n_string.ToList();
            int onecount =0;
            for(int j = sen.Count-1; j>=0; j--)
            {
                if(sen[j] == '1')
                {
                    onecount++;
                }
                else break;
            }
            if(onecount<2) 
            {
                answer[i] =numbers[i]+1;
                continue;
            }
            else 
            {
                if(sen.Count ==onecount)
                {
                    sen.Insert(0,'0');
                }
                sen[sen.Count-onecount]='0';
                sen[sen.Count-onecount-1] = '1';
                long result =0;
                int count =0;
                for(int k=sen.Count-1;k>=0; k--)
                {
                    if(sen[k]=='1') result += MyPow(2,count);
                    count++;
                }
                answer[i] = result;
            }
        }
        return answer;
    }
        public static long MyPow(long to1, long to2)
    {
        long num = 1;
        for (long i = 0; i < to2; i++)
        {
            num = num * to1;
        }
        return num;
    }
}

 느낀점 : 문제의 제한사항 때문에 반복문으로 해결하지 못하고 위에서 설명한 규칙을 찾아 해결해야하며,

굉장히 큰 숫자의 입력값이 들어오기 때문에 long타입의 거듭제곱 함수를 따로 만들어서 풀어줘야하였다.

문제의 난이도는 그렇게 높지 않지만 기본기가 부족하다면 한 없이 어려워지는 문제인 것 같다.