C++로 이진 문자열을 n회 변환한 뒤 i번째 문자 찾기

이진 문자열 bin이 주어졌을 때, 여기에 n번의 반복(변환)을 적용한다고 가정해 보겠습니다. 각 반복 단계에서 0은 "01"로, 1은 "10"으로 변환됩니다. 우리의 목표는 n번 반복을 모두 거친 최종 문자열에서 i번째 인덱스의 문자를 찾아내는 것입니다.

예를 들어 이진 문자열이 "101"이고 n = 2, i = 3이라고 가정해 보겠습니다. 첫 번째 반복 후에는 "100110"이 되고, 두 번째 반복 후에는 "100101101001"이 됩니다. 따라서 인덱스 3에 해당하는 문자는 '1'입니다.

문제 해결 접근 방법

이 문제는 다음 단계에 따라 해결할 수 있습니다.

• n번 반복하는 외부 루프를 실행하고, 각 반복마다 문자열 전체를 순회하는 내부 루프를 수행합니다.
  • 이진 문자열의 각 문자를 검사하여 '0'이면 임시 문자열(temp)에 "01"을 추가하고, '1'이면 "10"을 추가합니다.
  • 내부 루프가 종료되면 임시 문자열을 원래의 이진 문자열 변수에 대입합니다.
• 모든 반복이 완료된 최종 문자열에서 i번째 인덱스의 문자를 반환합니다.

C++ 예제 코드

#include<iostream>
using namespace std;
char getCharacter(string bin_str, int n, int i) {
   string temp = "";
   for (int x = 0; x < n; x++) {
      for (int y = 0; y < bin_str.length(); y++) {
         if (bin_str[y] == '1')
            temp += "10";
         else
            temp += "01";
      }
      bin_str = temp;
      temp = "";
   }
   return bin_str[i];
}
int main() {
   int n = 2;
   string bin = "101";
   cout << 3 << "rd character is: "<< getCharacter(bin, n, 3)<<endl;
   cout << 9 << "th character is: "<< getCharacter(bin, n, 9);
}

실행 결과

3rd character is: 1
9th character is: 0

시간 복잡도 분석

각 반복마다 문자열의 길이가 정확히 2배씩 늘어나므로, 초기 길이가 L인 문자열은 n회 반복 후 L × 2ⁿ 길이가 됩니다. 따라서 위 방식의 시간 복잡도는 O(L × 2ⁿ)입니다. n이 커지면 문자열 크기가 지수적으로 증가하기 때문에, 실전에서는 재귀적 성질(각 비트가 부분 트리 구조로 확장됨)을 활용해 문자열 전체를 만들지 않고 i번째 문자만 직접 계산하는 최적화 기법을 고려할 수 있습니다.