[Programmers] 2개 이하로 다른 비트(Lv.2)

풀이 소요시간 : 풀이 참고(실패)

특정 규칙을 찾지 않으면 시간초과로 실패가 나오는 문제였다. 단순 구현으로 문제를 풀었다가 2 차례의 시간초과를 맛보고 풀이를 참고하기로 마음먹었다.

짝수의 경우 바로 다음 수가 최적 값이다.

1100 -> 1101
11110 -> 11111

위와 같이 짝수는 항상 마지막 비트가 0이고, 마지막 비트를 1로 바꿔주면 최적값이 형성된다.

홀수의 경우 마지막 비트부터 탐색하여 처음 발견한 0을 1로 바꿔주고 바로 아래 1을 0으로 바꿔준다.

11011 -> 11101
1111 -> 10111

위와 같이 모든 자릿수가 1인 경우에도 해당된다.

너무 빠르게 포기하고 풀이를 참고한게 아닐까 하는 생각이 들었다. 다음부터 규칙을 찾아야하는 문제가 있다면 하나하나 직접 써보면서 규칙을 찾아보도록 하자.

전체 코드

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

using namespace std;

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