이진 문자열 bin이 하나 주어져 있다고 가정해 봅시다. 이 문자열에 n번의 반복(iteration)을 적용하는데, 각 반복마다 0은 '01'로, 1은 '10'으로 변환됩니다. 그 후 n번째 반복까지 완료된 문자열에서 i번째 인덱스에 해당하는 문자를 구하는 것이 목표입니다.
예를 들어 이진 문자열이 101이고 n = 2, i = 3이라고 해보겠습니다. 첫 번째 반복을 거치면 문자열은 100110이 되고, 두 번째 반복을 거치면 100101101001이 됩니다. 따라서 i번째(3번째) 인덱스에는 1이 위치하게 됩니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- n번 반복되는 외부 루프를 실행하고, 각 반복 안에서 문자열 전체를 순회하는 내부 루프를 실행합니다.
- 이진 문자열의 각 문자를 확인하여 '0'이면 임시 문자열(temp)에 "01"을 추가하고, '1'이면 "10"을 추가합니다.
- 내부 루프가 끝나면 임시 문자열을 원래 이진 문자열에 대입합니다.
- 모든 반복이 완료된 후 i번째 인덱스의 문자를 반환합니다.
예제 코드
#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번째 문자는: " << getCharacter(bin, n, 3) << endl;
cout << "9번째 문자는: " << getCharacter(bin, n, 9);
}실행 결과
3번째 문자는: 1 9번째 문자는: 0
참고 사항
위 방법은 문제의 요구사항을 직관적으로 구현한 것입니다. 다만 각 반복마다 문자열 길이가 두 배씩 늘어나기 때문에 시간 복잡도는 O(2ⁿ × 초기 길이), 공간 복잡도 역시 O(2ⁿ)이 됩니다. 따라서 n이 커지면 메모리 사용량이 기하급수적으로 증가할 수 있다는 점을 유의해야 합니다.