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

 

 

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

 

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

프로그래머스

---

 

 

해결방안

 

비트 조작(Bit Manipulation)

비트 연산(Bit Operation)

이 문제는, 짝수일 경우에는 1을 더하고 홀수일 경우에는 이진수 표현에서 가장 낮은 자리의 '0'을 '1'로 바꾸는 연산을 수행.

비트 조작을 통해 숫자를 최소한으로 증가시켜 다음 큰 수를 구하는 문제다.

 

---

 

 

처음 시도한 코드 - 시간초과

 

#include <string>
#include <vector>
using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;

    for(int i=0; i<numbers.size(); i++)
    {
        long long tmp = numbers[i];
        string bnum = "";
	    while(tmp > 0)
	    {
            string newNum = to_string(tmp % 2);
            bnum = newNum + bnum;
            tmp /= 2;
	    }

        long long binary = numbers[i];
        while(true)
        {
            binary++;
            long long temp = binary;
            string newBinary = "";
            while (temp > 0)
            {
                newBinary = to_string(temp % 2) + newBinary;
                temp /= 2;
            }

            int cnt = 0;
            if (bnum.size() == newBinary.size()) cnt = 0;
            else if (bnum.size() < newBinary.size()) cnt = newBinary.size() - bnum.size();

        	int back = newBinary.size() - 1;

            for (int i = bnum.size()-1; i>=0; i--)
            {
                if (bnum[i] != newBinary[back]) cnt++;
                
                back--;

                if (cnt > 2) break;
            }
            
            if (cnt<=2){
                answer.emplace_back(binary);
                break;
            }
        }
    }
    
    return answer;
}

 

---

 

정답 코드

 

주어진 수가

• 짝수인 경우:  짝수일 경우, 이진수에서 가장 낮은 비트가 0이므로, 이를 1로 바꾸면 2비트 이하의 차이를 가지는 다음 큰 숫자를 얻을 수 있다.
• 홀수인 경우: 가장 낮은 0 비트를 찾는다. 이 비트를 1로 바꾸면 2비트 이하의 차이를 가지는 다음 큰 숫자를 얻을 수 있다. 다시말하자면, 가장 낮은 자리부터 검사해서 처음으로 등장하는 연속된 1의 끝을 0으로 바꾸고, 그 다음 자리를 1로 바꾸면 된다.

 

#include <vector>
using namespace std;

vector<long long> solution(vector<long long> numbers){
    vector<long long> answer;

    for (int i = 0; i < numbers.size(); i++) 
    { 
        if (numbers[i] % 2 == 0) { // 짝수
            answer.push_back(numbers[i] + 1); // 다음 큰 숫자를 answer에 추가
        }
        else { // 홀수
            long long bit = 1; // 비트를 조작하기 위한 변수를 선언하고 초기값으로 1을 설정

        	while (true) 
        	{
                // 해당 숫자와 비트를 AND 연산한 결과가 0이면 반복문을 종료.
                // 이는 가장 낮은 자리의 0 비트를 찾기 위한 작업이다.
                if ((numbers[i] & bit) == 0) 
                    break;

                bit *= 2; // 비트를 왼쪽으로 한 자리 이동
            }
            bit = bit / 2; // 왼쪽으로 이동한 비트를 오른쪽으로 한 자리 이동해서 원래 위치로 되돌림

            answer.push_back(numbers[i] + bit); // 해당 숫자에 비트를 더하고 결과 벡터에 추가. 이는 홀수인 숫자에서 가장 낮은 자리의 0을 1로 바꾸는 연산이다.
        }
    }

    return answer; 
}

 

 

---