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

 

 

문제 설명

양의 정수 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

---

 

 

 

 

 

 

풀이

접근법이 어려운 문제이다.

완전 탐색을 이용하여 모든 수를 비교하여 답을 찾을 수 있지만, 시간초과에 걸릴 것이다.

따라서, 다른 접근법이 필요하다.

비트의 성질을 이용하면 되는데, 비트가 2개 이하로 다른 수 중 가장 작은 수는 오른쪽에서 가장 먼저 나타나는 0을 찾으면 쉽게 구할 수 있다.

오른쪽에서 가장 먼저 나타난 0을 1로 바꾸고 그 오른쪽비트를 0으로 바꾸면 가장 작은 수가 된다.

0이 아닌 비트를 바꾸게 되면 다른 비트들이 연쇄적으로 바뀔 수 있기 때문이다.

이때, 예외인 상황이 2가지 있다.

• 모든 비트가 1인경우
• 제일 오른쪽 비트가 0인 경우

우선, 첫 번째 경우에는 0을 찾을 수 없지만 적용하는 규칙은 동일하다.

두 번째 경우는 0인 비트 오른쪽에 1을 뺄 수 없기 때문에 예외가 발생하는데 이 경우에는 0을 1로만 바꾸면 된다.

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <cmath>

using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    for(auto num : numbers)
    {
        //find 0
        long long temp = num;
        int n = 0;
        
        while(temp > 0)
        {
            if(temp % 2 == 0) break;
            
            temp /= 2;
            n++;
        }
        
        if(n == 0) answer.push_back(num+1);
        else
        {
            num += pow(2,n);
            num -= pow(2, n-1);
            
            answer.push_back(num);
        }
    }
    
    return answer;
}

---