C++에서 반복적인 반전 및 추가 연산으로 생성된 이진 문자열의 k번째 비트 찾기

초기값이 "0"인 이진 문자열이 있다고 가정해 보겠습니다. 매 반복(iteration)마다 현재 문자열을 반전시킨 후(0은 1로, 1은 0으로 변경), 그 결과를 기존 문자열 뒤에 덧붙입니다. 이 과정을 n번 수행한 뒤, 완성된 문자열에서 k번째 비트를 찾는 것이 이 문제의 목표입니다.

예를 들어 반복 횟수가 4이고 k = 7이라면, 문자열은 아래 표와 같이 변화합니다.

따라서 7번째 비트는 1입니다.

접근 방법

핵심 아이디어는 간단합니다. 각 반복 단계에서 현재 문자열의 보수(complement)를 계산하고, 이를 원래 문자열 뒤에 이어 붙이는 것입니다. 모든 반복이 끝난 최종 문자열에서 인덱스 k에 해당하는 문자를 반환하면 원하는 답을 얻을 수 있습니다.

C++ 구현 예제

#include<iostream>
using namespace std;

// 문자열의 각 비트를 반전시켜 보수 문자열을 반환하는 함수
string getComplement(string bin){
    string temp = "";
    for(int i = 0; i<bin.length(); i++){
        if(bin[i] == '0')
            temp += "1";
        else
            temp += "0";
    }
    return temp;
}

// n번 반복 후 k번째 문자를 반환하는 함수
char getCharacter(string bin_str, int n, int k) {
    string res = bin_str;
    for(int i = 0; i<n; i++){
        res += getComplement(res);
    }
    return res[k];
}

int main() {
    int n = 4;
    string bin = "0";
    cout << 7 << "th character is: " << getCharacter(bin, n, 7);
}

출력 결과

7th character is: 1

복잡도 분석

문자열의 길이는 반복할 때마다 두 배씩 늘어나므로, n번 반복 후 문자열 길이는 2ⁿ이 됩니다. 따라서 이 알고리즘의 시간 복잡도와 공간 복잡도는 모두 O(2ⁿ)입니다.