C++로 피보나치 수 위치에 대문자 'O'를 넣은 이름 문자열 만들기

숫자 n이 주어졌을 때, 아말(Amal)은 반려동물에게 이름을 지어주려고 합니다. 이름은 알고리즘에 따라 결정되며, 길이는 정확히 n자입니다.

이름을 구성하는 규칙은 다음과 같습니다.

• 이름의 i번째 문자 위치(1부터 n까지 번호 매김)
• i가 피보나치 수라면 대문자 'O'를 사용
• 그렇지 않다면 소문자 'o'를 사용

예시

예를 들어 n = 10이 입력으로 주어지면, 피보나치 수열의 첫 번째 항들은 1, 2, 3, 5, 8... 이므로 출력 결과는 다음과 같습니다.

OOOoOooOoo

1번째, 2번째, 3번째, 5번째, 8번째 자리만 대문자 'O'이고 나머지는 모두 소문자 'o'인 것을 확인할 수 있습니다.

해결 접근 방법

이 문제는 다음 단계를 통해 해결할 수 있습니다.

1. 길이가 n이고 모든 문자가 'o'로 채워진 문자열 s를 생성합니다.
2. 두 변수 i와 j를 모두 1로 초기화한 뒤, i가 n 이하인 동안 반복하면서 s[i-1]을 'O'로 변경합니다.
3. 각 반복 후에는 i를 j만큼 증가시키고, j는 i-j 값으로 갱신하여 피보나치 수열을 따라가도록 합니다.
4. 반복이 끝나면 완성된 문자열 s를 반환합니다.

여기서 핵심은 별도의 배열 없이 두 변수만으로 피보나치 수열을 생성한다는 점입니다. i는 현재 피보나치 수, j는 바로 앞의 피보나치 수를 나타내며, 갱신 순서(i += j 실행 후 j = i - j) 덕분에 기존 값을 잃지 않고 수열을 진행할 수 있습니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
string solve(int n){
   string s(n, 'o');
   for (int i = 1, j = 1; i <= n; i += j, j = i - j)
      s[i - 1] = 'O';
   return s;
}
int main(){
   int n = 10;
   cout << solve(n) << endl;
}

입력

10

출력

OOOoOooOoo

복잡도 분석

이 알고리즘의 시간 복잡도는 O(log n)입니다. 피보나치 수는 지수적으로 증가하기 때문에 n 이하의 피보나치 수의 개수는 로그 스케일로 늘어나기 때문입니다. 공간 복잡도는 결과 문자열 저장을 위해 O(n)이 필요합니다.