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

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

프로그래머스

 

해결 방법

숫자를 1씩 증가시켜서 검사할 경우, 시간초과가 발생한다. 

• 값이 0010 이라면, 그다음으로 큰 수는 0011 이다. 처음으로 나오는 0을 1로 변환했다.
• 값이 0001 이라면, 그 다음으로 큰 수는 0010 이다. 처음으로 나오는 0을 1로 변환하고, 그 앞의 1을 0으로 변환했다.

이 내용을 종합하면, 2비트 이하로  다르면서 가장 작은 수를 구하는 방법은 다음과같다.

1. num을 2진수변환하면서 배열 digits에 넣는다. digits[0] 이 가장 낮은자리수값이다.(거꾸로저장됨)
2. 가장 처음으로 0이 나오는 index를 찾는다.
3. 그 0을 1로 바꾼다.
4. 0앞에 1이 있다면, 바로앞의 1을  0으로 바꿔준다.
5. 바뀐 digits를 이용해 10진수로 변환후 반환한다.

#include <string>
#include <vector>
#include <cmath>
using namespace std;

long long func(long long num){
    vector<int> digits;
    
    int firstZero = -1;
    while(num!=0){
        int val = num%2;
        digits.push_back(val);
        if(val == 0 && firstZero == -1) firstZero = digits.size()-1; //처음으로 0이 나오는 인덱스를 찾음.
        num /=2 ;
    }
    
    //0이 하나도 없다면, 맨뒤에 0을 넣어주고 firstZero 갱신
    if(firstZero == -1 ){
        digits.push_back(0);
        firstZero = digits.size()-1;
    }
    
    //0을 1로 바꾸고, 만약 앞에 1이 있다면 0으로 변경
    digits[firstZero] = 1;
    if(firstZero -1 >=0 && digits[firstZero-1] == 1) digits[firstZero-1] = 0;
    
    //숫자로변환
    long long answer =0;
    for(int i=0; i<digits.size(); i++){
        if(digits[i] == 0) continue;
        answer += pow(2,i);
    }
    return answer;
}
vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    for(int i= 0; i<numbers.size(); i++){
        answer.push_back(func(numbers[i]));
    }
    return answer;
}