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

2개 이하로 다른 비트

문제 링크

2개 이하로 다른 비트

분석

다음 규칙을 가진 수를 찾아야 합니다.

1. 주어진 수 보다 크고, 가장 가까운 수
2. 비트가 1개 혹은 2개가 다른 수

주어진 수가 짝수의 경우 가장 오른쪽 끝 비트를 1로 변경하면 됩니다.

예를 들어, 다음과 같습니다.

수	비트	정답	비트
2	10	3	11
4	100	5	101
6	110	7	111
8	1000	9	1001
10	1010	11	1011

즉, $x + 1$와 같습니다.

주어진 수가 홀수인 경우 가장 오른쪽 끝 비트에서부터 왼쪽으로 0을 찾고, 0을 1로 변경하고 0의 오른쪽 비트를 1로 변경하면 됩니다.

예를 들어, 다음과 같습니다.

수	비트	정답	비트
1	1	2	10
3	11	5	101
5	101	6	110
7	111	11	1011
9	1001	10	1010
11	1011	13	1101

풀이

#include <vector>

using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    // numbers 순회
    for (long long number : numbers)
    {
        
        if (number % 2 == 0)
        {
            // 짝수인 경우
            answer.push_back(number + 1);
        }
        else
        {
            // 홀수인 경우

            // 0을 찾기 위한 비트 마스크
            long long bit = 1;
            
            // 0을 찾을 때까지 비트를 왼쪽으로 이동
            while (number & bit)
            {
                bit <<= 1;
            }
            
            // 찾은 위치의 0을 1로 바꾼 수
            long long zeroToOne = number + bit;

            // 찾은 위치의 오른쪽에 1을 0으로 바꾸기 위한 수
            long long OneTozero = bit >> 1;
            
            answer.push_back(zeroToOne - OneTozero);
        }
    }
    
    return answer;
}

number + bit는 찾은 0을 1로 바꿔 줍니다.

예를 들어, 다음과 같습니다.

$7 + 8 = 15$
$0111 + 1000 = 1111$

0을 1로 바꾼 후 오른쪽의 1은 0으로 바꿔줘야 하므로, 다음과 같습니다.

$15 - 4 = 11$
$1111 - 0100 = 1011$

성능 요약

시간 복잡도는 $O(n)$입니다.

• numbers를 순회하는 반복문 $O(n)$
• numbers의 요소 최대값은 $10^15$이므로, 2진수로 보면 최대 53비트 $O(53 \approx 1)$
• $O(n \tiems 1)$

공간 복잡도는 $O(n)$입니다.

• 반환할 결과값을 저장할 answer $O(n)$

테스트 1 〉 통과 (0.21ms, 4.21MB)
테스트 2 〉 통과 (29.99ms, 27.7MB)
테스트 3 〉 통과 (0.03ms, 4.17MB)
테스트 4 〉 통과 (0.17ms, 4.15MB)
테스트 5 〉 통과 (0.20ms, 4.21MB)
테스트 6 〉 통과 (0.19ms, 4.21MB)
테스트 7 〉 통과 (25.78ms, 25.7MB)
테스트 8 〉 통과 (25.07ms, 25MB)
테스트 9 〉 통과 (24.85ms, 24.1MB)
테스트 10 〉 통과 (30.68ms, 27.8MB)
테스트 11 〉 통과 (35.64ms, 27.8MB)