Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 마법 문자열(Magical String): 처음 N개 문자에서 '1' 개수 구하기

'1'과 '2'로만 이루어진 문자열 S가 있다고 상상해 보세요. 이 문자열은 특별한 성질 때문에 마법 문자열(Magical String)이라고 불리는데, 그 비결은 문자 '1'과 '2'가 연속해서 등장하는 횟수를 순서대로 이어 붙였을 때 그 결과가 놀랍게도 문자열 S 자신이 된다는 점입니다.

마법 문자열 S의 첫 부분은 다음과 같습니다.

S = "1221121221221121122……"

S에서 연속된 같은 문자들을 그룹으로 묶어 보면 다음과 같습니다.

1 | 22 | 11 | 2 | 1 | 22 | 1 | 22 | 11 | 2 | 11 | 22 ……

각 그룹의 길이, 즉 '1' 또는 '2'가 연속해서 나타난 횟수를 차례대로 적어 보면 다음과 같습니다.

1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2 ……

흥미롭게도 이 수열은 원래 문자열 S와 정확히 일치합니다. 바로 이러한 자기 참조적(self-referential) 성질이 이 문자열을 "마법"이라고 부르는 이유입니다.

문제 정의

정수 N이 주어졌을 때, 마법 문자열 S의 처음 N개 문자 가운데 '1'의 개수를 구하는 것이 목표입니다.

예시: 입력이 6이라면 출력은 3입니다. 마법 문자열의 처음 6개 문자는 "122112"이며, 여기에는 '1'이 세 개 포함되어 있기 때문입니다.

해결 접근 방식

이 문제는 두 포인터(two pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 한 포인터(head)는 "다음 문자를 몇 번 반복할지"를 알려 주는 값을 가리키고, 다른 포인터(tail)는 새 문자를 채워 넣을 위치를 가리킵니다. 즉, 배열의 앞부분을 읽으면서 뒷부분을 동시에 채워 나가는 방식입니다.

구체적인 알고리즘 단계는 다음과 같습니다.

  1. n ≤ 0이면 0을 반환하고, n ≤ 3이면 1을 반환합니다.
  2. ret := 1로 초기화하고, 크기가 n인 배열 arr을 준비합니다.
  3. arr[0] := 1, arr[1] := 2, arr[2] := 2로 초기값을 설정합니다.
  4. head := 2, tail := 3, num := 1로 초기화합니다.
  5. tail < n인 동안 다음을 반복합니다.
    • i를 0부터 arr[head] − 1까지 반복하면서:
      • arr[tail] := num을 대입합니다.
      • num이 1이고 tail < n이면 ret을 1 증가시킵니다.
      • tail을 1 증가시킵니다.
      • tail ≥ n이 되면 내부 반복문을 종료합니다.
    • num = num XOR 3으로 갱신합니다. (XOR 3은 값이 1 ↔ 2로 전환되는 효과가 있습니다.)
    • head를 1 증가시킵니다.
  6. 최종적으로 ret을 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int magicalString(int n) {
      if(n <= 0) return 0;
      if(n <= 3) return 1;
      int ret = 1;
      vector <int> arr(n);
      arr[0] = 1;
      arr[1] = 2;
      arr[2] = 2;
      int head = 2;
      int tail = 3;
      int num = 1;
      while(tail < n){
         for(int i = 0; i < arr[head]; i++){
            arr[tail] = num;
            if(num == 1 && tail < n) ret++;
            tail++;
            if(tail >= n) break;
         }
         num ^= 3;
         head++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.magicalString(6));
}

입력

6

출력

3

동작 원리 살펴보기

이 알고리즘의 핵심은 이미 확정된 배열의 앞부분(arr[head])을 "반복 횟수 지시자"로 활용해 뒷부분(arr[tail])을 채워 나간다는 점입니다. 문자열의 접두사가 곧 생성 규칙이 되는 셈이므로, 별도의 규칙을 따로 저장하지 않고도 필요한 길이만큼 마법 문자열을 생성할 수 있습니다.

또한 num ^= 3 연산은 1과 2를 번갈아 전환하는 우아한 기법입니다. 1 XOR 3 = 2이고, 2 XOR 3 = 1이기 때문에 조건문 없이 간단히 값을 뒤집을 수 있습니다.

성능 면에서 이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로, 문자열을 직접 하나씩 검증하는 방식보다 훨씬 효율적입니다.