문제 77885. 2개 이하로 다른 비트

문제 링크

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

프로그래머스

 

 

난이도 :  Lv.2

 

문제 요약 설명

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

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

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

입력

• 정수들이 담긴 배열 numbers

입력 제한

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

입력 예제

// input
[2,7]

// ans
[3,11]

 

풀이 방식

2개 이하로 다른 비트는 총 0 -> 1, 1 -> 0, 01 -> 10, 00 -> 11로 4가지의 경우의 수가 있다. 이 때, 제일 작은 수가 나오는 경우는 0 -> 1, 01 -> 10밖에 없다. 1 -> 0은 "x보다 크고"라는 규칙에 위배되고, 00 -> 11은 0->1보다 항상 클 수밖에 없기 때문이다.

따라서, 이 2가지의 경우를 체크하면 정답을 구할 수 있다.

 

정답 코드 

#include <bits/stdc++.h>
#include <cmath>

#define MAXLEN 64

using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    for(long long elem : numbers){
        
        // 예외 처리: 값이 0이면 정답은 1이다. (모든 비트가 0인 경우 제외).
        if(elem == 0){
            answer.push_back(1);
            continue;
        }
        
        vector<int> v1(MAXLEN);
        long long temp_elem = elem;
        for(int idx = 0; temp_elem > 0; idx++){
            v1[idx] = temp_elem % 2;
            temp_elem /= 2;
        }
               
       
        // 0 -> 1
        long long a = 1;
        for(int i = 0; i < v1.size(); i++){
            // 가장 작은 0을 찾고 해당 위치를 1로 바꾼 것이 답.
            if(v1[i] == 0){
                a = a << i;   
                break;
            }
        }
        
        // 01 -> 10
        long long b = 1;
        for(int i = 1; i < v1.size(); i++){
            // 가장 작은 01 패턴을 찾고 해당 1의 값이 답.
            if(v1[i] == 0 && v1[i-1] == 1){  
                // 숫자는 기본 int형이다. 1을 << 하게되면 int형이라 오버플로우가 발생할 수 있다.
                b = (b << (i-1));
                break;
            }
        }
        
        answer.push_back(elem + min(a, b));
    
    }
    return answer;
}