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

문제

 

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

프로그래머스

 

 

문제풀이

 

처음엔 bitset, xor연산을 이용해서 구하려 했는데 테스트케이스 10, 11번에서 시간초과가 떠서 방법을 바꿨다.

최하위 비트에서부터 시작해서 0인 자리를 찾고 0인 자리와 그 아래 자리의 비트를 반전시키면 된다.

주어지는 숫자의 최대값은 10^15 이기 때문에 넉넉하게 bitset을 60자리로 표현하였다.

 

        for (int idx = 0; idx < 60; ++idx) {
            if (num.test(idx) == 0) {
                num.flip(idx);
                if (idx != 0)
                    num.flip(idx - 1);
                answer[num_idx] = num.to_ullong();
                break;
            }
        }

test(idx)는 idx번째 비트를 확인하는 함수이다.

flip(idx)는 idx번째 비트를 반전시키는 함수이다.

두 비트, 또는 한 비트를 반전시키고 bitset to ull함수를 통해 long long 값으로 바꿔준다.

 

 

코드

#include <string>
#include <vector>
#include <bitset>
#define ll long long
using namespace std;


vector<ll> solution(vector<ll> numbers) {
    vector<ll> answer(numbers.size(), 0);

    for (int num_idx = 0; num_idx < numbers.size(); ++num_idx) {
        bitset<60>num = numbers[num_idx];
        for (int idx = 0; idx < 60; ++idx) {
            if (num.test(idx) == 0) {
                num.flip(idx);
                if (idx != 0)
                    num.flip(idx - 1);
                answer[num_idx] = num.to_ullong();
                break;
            }
        }
    }

    return answer;
}