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

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

조건

1. 주어진 수보다 커야 함2. 비트(2진수)로 표현했을 때 각 자리수가 2개 이하로 달라야 함

3. 위 두 가지를 만족하는 최소 값

 

짝수라면?

비트의 끝은 무조건 0이므로 1로 바꾸어주면 조건이 성립

- f(n) = n + 1

ex) 10 -> 11, 100000 -> 100001 ...

 

홀수라면?

각 자리수가 2자리를 초과하여 다르면 안되고, 주어진 수보다 커야 하므로

마치 시프트 연산하듯 0과 1의 자리를 바꾸어줘야 함 ( 2자리 변경 )

- 0과 1의 자리를 바꿔준 경우에서 가장 작은 수를 만들기 위해선 0의 바로 옆 비트와 자리를 바꿔야 함

-> 오른쪽부터 비트를 확인하여 0이 나오면 1로 바꾸고 바로 오른쪽 비트를 0으로 바꿔줌

즉, 오른쪽 비트부터 체크하여 처음 나오는 01을 10으로 바꿀 경우 성립

ex) 0111 -> 1011, 1001 -> 1010 ...

 

주석 참조

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

    public class Solution
    {
        public long[] solution(long[] numbers)
        {
            var answerList = new List<long>();

            for (int i = 0; i < numbers.Length; i++)
            {
                if (numbers[i] % 2 == 0) // 짝수라면
                    answerList.Add(numbers[i] + 1);
                else // 홀수라면
                    answerList.Add(Function(numbers[i]));
            }

            return answerList.ToArray();
        }

        // 홀수일 경우 조건에 부합하는 숫자를 찾아 리턴
        public long Function(long num)
        {
            var sb = new StringBuilder();

            // 2진수 변환
            while (num != 0)
            {
                sb.Insert(0, (num % 2).ToString());
                num /= 2;
            }
            sb.Insert(0, "0"); // 맨 앞에 0 추가 (전부 다 1일경우 예외처리)

            // 홀수이므로 오른쪽 맨 끝은 무조건 1이 됨 
            for (int i = sb.Length - 2; i >= 0; i--)
            {
                // 처음 0 자리를 1로 바꿈
                if (sb[i] == '0')
                {
                    // 마치 쉬프트 연산하듯 01 -> 10으로 바꿈
                    sb[i] = '1';
                    sb[i + 1] = '0';
                    break;
                }
            }

            // 10진수 변환
            return Convert.ToInt64(sb.ToString(), 2);
        }
    }