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

Kim Yuhyeon·2024년 3월 23일

알고리즘

알고리즘 + 자료구조

목록 보기

160/161

문제

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

접근 방법

1차 시도
다른 부분을 찾기 위해 XOR 연산을 사용하였다.
각 num 부터 1씩 더하며 XOR 연산 한 값에서 1의 개수를 세어 1이나 2면 답이다.

2차 시도
모두 찾는 방식이 시간 초과 요인이라고 생각하였다.
때문에 규칙을 찾아 보니,
짝수는 무조건 끝자리수가 0으로 끝나서 1만 더해주면 되었다.
홀수의 경우

가장 오른쪽에 있는 0을 1로 바꾸면 1자리 비트만 바뀐다. 대신 값이 증가할 수 있으므로 이거 보다 작게 1자리 비트를 더 바꾸기 위해서, 가장 오른쪽에 있던 0 자리 뒷자리를 0으로 바꾸어준다.

가장 오른쪽에 있는 0을 찾기 위해서는
2^0, 2^1, 2^2, 2^3 ... 을 & 연산하여 0이 나오면 해당 자리가 0이다.

그리고 결국 그 뒷자리의 1을 0으로 바꿔야 하기 때문에
원래 수에서 (위에서 구한 자리수/2)를 더하면 위의 2개를 한번에 하는 셈이다. ~~처음엔 직접 바꿔주려 했다; 바보 ..~~

ex. 0111(7)

b = 1 -> 0111 & 0001 = 0001
b = 2 -> 0111 & 0010 = 0010
b = 4 -> 0111 & 0100 = 0100
b = 8 -> 0111 & 1000 = 0000 => 찾았다

가장 오른쪽에 있는 0 -> 1 : 1111(15)
가장 오른쪽에 있던 0 자리 뒷자리 1 -> 0 : 1011 (11)
= 7+(8/2) = 11

풀이

1차 시도 : 시간 초과

#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <iostream>

#define MAX 50
using namespace std;

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

    // 2진수로 변환 
    for(long long n : numbers) { // 100,000
        
        bool found = false;
        bitset<MAX> A(n);

        while(!found) {
            bitset<MAX> B(++n);
            bitset<MAX> result = A ^ B;

            // bitset 중에서 1인 비트의 개수를 반환
            int cnt = result.count();

            if (cnt >= 1 && cnt <= 2) {
                found = true;
                answer.push_back(n);
            }
        }



    }
    

    return answer;
}

결과

테케 10, 11 시간초과
정확성: 81.8

2차 시도 : 통과

#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <iostream>


using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    for(long long num : numbers) {
        if (num % 2 == 0) {
            answer.push_back(num + 1);
        } else {
            long long b = 1;
            while(true) {
                if ((num & b) == 0) {
                    break;
                }    
                b *= 2; 
            }
            
            answer.push_back(num + (b/2));
        }
    }    

    return answer;
}