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

 이 문제는 규칙성을 찾아서 푸는 문제이다. 일단 입력 배열의 길이가 최대 100,000 이고, 배열 원소의 최대 크기는 10^15이다. 즉, 1,000,000,000,000,000 이고, 이를 이진수로 바꾸면

11 1000 1101 0111 1110 1010 0100 1100 0110 1000 0000 0000 0000 최대 길이 50의 이진수가 나온다. 따라서 100,000 길이 배열의 모든 원소가 10^15인 숫자를 이진수로 바꾸는데까지는 시간 초과가 걸리지 않는다.

 

 

 처음에는 배열의 한 숫자에 대해서 해당 숫자 + 1부터 루프를 돌려 이진수로 바꾸고, 비트가 맞지 않는 수를 세어 처음으로 2 이하인 수를 리턴했으나, 이런 식으로는 시간 초과가 난다. 단적인 예로 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 인 숫자의 다음 f(x) 를 구하려고 한다면 완전 탐색으로는 시간 초과가 날 것이 분명하다. 그러므로 규칙성을 찾아야 하는데, 다음과 같은 알고리즘을 생각했다.

1. number를 이진수로 바꾼 마지막이 0으로 끝나면, number + 1이 정답
2. 만약 1로 끝나면, 마지막으로 0이 나온 위치와 그 위치 + 1을 서로 바꾸어 준 숫자가 정답

 2번이 정답이 나올지 의문이었는데, 만약 01로 끝났다면 10으로 바꾸는게 최적이고, 011로 끝났다면 101로 바꾸는게 최적, 0111로 끝났다면 1011로 바꾸는게 최적임을 직접 세어보면 알 수 있었다. 이를 코드로 바꾸면 시간 안에 문제를 풀 수 있다.

 

 

#include <string>
#include <vector>

using namespace std;

string convert(long long number) {
    if (number == 0) {
        return "0";
    }
    
    string result = "";
    
    while (number > 0) {
        result = to_string(number % 2) + result;
        number /= 2;
    }
    
    return result;
}

long long pow[51];

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    long long temp = 1;
    
    for (int i = 0; i < 51; i++) {
        pow[i] = temp;
        temp *= 2;
    }
    
    for (long long number : numbers) {
        string present = convert(number);
        
        if (present[present.size() - 1] == '0') {
            answer.push_back(number + 1);
            continue;
        }
        
        int indexOfZero = -1;
        for (int i = present.size() - 1; i >= 0; i--) {
            if (present[i] == '0') {
                indexOfZero = i;
                break;
            }
        }
        
        if (indexOfZero == -1) { // 모든 수가 1인 경우
            present = '1' + present;
            present[1] = '0';
            
            // 숫자로 변경
            long long result = 0;
            for (int i = 0; i < present.size(); i++) {
                result += (present[i] - '0') * pow[present.size() - i - 1];
            }
            answer.push_back(result);
            
            continue;
        }
        
        present[indexOfZero] = '1';
        present[indexOfZero + 1] = '0';
        
        // 숫자로 변경
        long long result = 0;
        for (int i = 0; i < present.size(); i++) {
            result += (present[i] - '0') * pow[present.size() - i - 1];
        }
        answer.push_back(result);
    }
    
    return answer;
}