[Programmers Level2] 2개 이하로 다른 비트(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

프로그래머스

 

 

[문제 설명]

 

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

• x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

 

예를 들어,

• f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

 

수	비트	다른 비트의 개수
2	000...0010
3	000...0011	1

• f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

 

수	비트	다른 비트의 개수
7	000...0111
8	000...1000	4
9	000...1001	3
10	000...1010	3
11	000...1011	2

 

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

 

 

[제한 사항]

 

 

• 1 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 1015

 

 

[입출력 예]

 

 

numbers	result
[2,7]	[3,11]

 

 

[입출력 예 설명]

 

 

입출력 예 #1

• 문제 예시와 같습니다.

 

 

[문제 풀이]

 

STL bitset을 사용하였다.

처음엔 주어진 수에 +1씩 하며 XOR 연산을 통해 1의 개수가 2개 이하가 되는 경우 정답 배열에 추가하는 방식이였다.

하지만 테스트 케이스 10, 11에 시간 초과가 발생했다.

아래와 같이 코드를 작성했었는데 여기서 더이상 시간을 줄일 수 있는 방법이 생각나질 않았다.

#include <string>
#include <vector>
#include <bitset>
#include <utility>
#include <cmath>
#include <iostream>
using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    int len = numbers.size();
    for(int i = 0; i < len; ++i) {
        bitset<50> gBit(numbers[i]);
        while(true) {
            bitset<50> gTemp(++numbers[i]);
            int count = (gBit ^ gTemp).count();
            if(count >= 3) continue;
            if((count == 1) || (count == 2)) {
                answer.emplace_back(numbers[i]);
                break;
            }
        }
    }
    return answer;
}

 

결국은 규칙을 찾게되어 코드를 구현했다. 규칙은 아래와 같다.

 

1) 주어진 수가 짝수인 경우 비트가 다른 지점이 2개 이하이면서 제일 작은 수는

➜ 맨 오른쪽 끝 비트가 1로 변경이 되는 것이다.

 

예를 들면

10진수 4를 2진수로 나타내면 100 이다.

맨 오른쪽 끝 비트 100 이 1로 변경되면 101 즉 5가 되는데 비트가 다른 지점이 2개 이하이면서 제일 작은 수이다.

 

2) 주어진 수가 홀수인 경우 비트가 다른 지점이 2개 이하이면서 제일 작은 수는

➜ 맨 오른쪽에서 첫번째로 발견하는 0인 비트를 1로 변경하고 이전 비트를 반전시키는 것이다.

 

예를 들면

10진수 13을 2진수로 나타내면 1101 이다.

맨 오른쪽에서 첫번째로 발견하는 0인 비트 1101 를 1로 변경하고 1111

이전 비트 1111 을 반전시킨다. 1110

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/Programmers: Study Programmers for Coding Test

 

 

#include <string>
#include <vector>
#include <bitset>
#include <utility>
#include <cmath>
#include <iostream>
using namespace std;

vector<unsigned long long> solution(vector<long long> numbers) {
    vector<unsigned long long> answer;
    int len = numbers.size();
    for(int i = 0; i < len; ++i) {
        bitset<50> gBit(numbers[i]);
        if(numbers[i] % 2 == 0) {
            // 짝수
            gBit[0] = true;
        } else {
            for(int i = 0; i < gBit.size(); ++i) {
                if(gBit[i] == false) {
                    gBit[i] = true;
                    gBit[i - 1] == true ? gBit[i - 1] = false : gBit[i -1] = true;
                    break;
                }
            }
        }
        answer.emplace_back(gBit.to_ullong());
    }
    return answer;
}