C++에서 반복 횟수 세기: 사이클 탐지로 효율적으로 풀기

문제 개요

비어 있지 않은 두 문자열 s1과 s2(각각 최대 100자), 그리고 0 이상 10⁶ 이하 범위의 두 숫자 n1과 n2가 주어집니다. 이를 바탕으로 S1 = [s1, n1], S2 = [s2, n2]라고 정의합니다.

여기서 S = [s, n]은 문자열 s를 n번 이어 붙인 문자열을 의미합니다. 예를 들어 ["ab", 4]는 "abababab"가 됩니다.

반대 방향의 개념도 하나 정의할 필요가 있습니다. 문자열 s2에서 일부 문자를 제거했을 때 s1이 만들어진다면, "s1을 s2로부터 얻을 수 있다"고 표현합니다. 따라서 "abc"는 "abdbec"에서 얻을 수 있지만, "acbbe"에서는 얻을 수 없습니다.

이 문제의 목표는 [S2, M]을 S1로부터 얻을 수 있는 최대 정수 M을 찾는 것입니다.

예를 들어 입력이 s1 = "acb", n1 = 4, s2 = "ab", n2 = 2라면 출력은 2입니다. S1 = "acbacbacbacb"에서 S2인 "abab"를 두 번 이어 붙인 "abababab"를 만들 수 있지만, 세 번 반복한 형태는 더 이상 만들 수 없기 때문입니다.

풀이 접근 방식

이 문제의 핵심 아이디어는 사이클(주기) 탐지입니다. s1을 n1번 반복해 만든 긴 문자열을 앞에서부터 훑으며 s2의 문자를 순서대로 매칭합니다. s2를 한 바퀴 완전히 돌고 난 뒤 s1 내부 위치가 첫 완주 시점과 동일해지면, 이후에는 같은 패턴이 계속 반복됩니다. 이 지점을 발견하면 남은 구간을 한 번에 건너뛸 수 있어 연산량을 크게 줄일 수 있습니다.

구체적인 절차는 다음과 같습니다.

사전 검사: s2의 각 문자 c에 대해, c가 s1에 존재하지 않으면 즉시 0을 반환합니다.
초기화: 포인터 p1 := 0, p2 := 0, 기준점 mark := 0으로 설정합니다.
순회: p1이 s1의 길이 × n1보다 작은 동안 다음을 반복합니다.
- c := s2[p2 mod s2의 길이]
- s1[p1 mod s1의 길이]가 c와 같아질 때까지(단, p1 < s1의 길이 × n1) p1을 증가시킵니다.
- p2를 1 증가시킨 뒤 p1도 1 증가시킵니다.
- p2 mod s2의 길이가 0이면(s2를 한 바퀴 완주한 경우):
  - p2가 s2의 길이와 같다면(첫 번째 완주): mark := p1로 기록합니다.
  - 그렇지 않고 p1 mod s1의 길이가 mark mod s1의 길이와 같다면(사이클 발견):
    - round := (s1의 길이 × n1 − p1) / (p1 − mark)
    - p1 := p1 + round × (p1 − mark)
    - p2 := p2 + round × (p2 − s2의 길이)
결과 반환: p2 / s2의 길이 / n2를 반환합니다.

왜 사이클 탐지가 필요한가?

n1과 n2는 최대 10⁶까지 커질 수 있습니다. 매칭 과정을 끝까지 일일이 시뮬레이션하면 최악의 경우 상당한 시간이 걸립니다. 반면 동일한 상태(s1 내 위치와 s2 내 위치의 조합)가 재등장하는 순간을 포착하면, 그 이후의 진행은 완전히 동일하게 반복되므로 나눗셈 한 번으로 남은 전체 구간을 처리할 수 있습니다.

C++ 구현 예제

아래 코드를 통해 실제 구현을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int getMaxRepetitions(string s1, int n1, string s2, int n2) {
      for (auto c : s2) {
        if (s1.find(c) == string::npos)
          return 0;
      }
      int p1 = 0, p2 = 0, mark = 0;
      while (p1 < s1.length() * n1) {
        char c = s2[p2 % s2.length()];
        while (s1[p1 % s1.length()] != c && p1 <s1.length() * n1)
        p1++;
        p2++;
        p1++;
        if (p2 % s2.length() == 0) {
          if (p2 == s2.length()) {
            mark = p1;
          }
          else if (p1 % s1.length() == mark % s1.length()) {
            int round = (s1.length() * n1 - p1) / (p1 - mark);
            p1 += round * (p1 - mark);
            p2 += round * (p2 - s2.length());
          }
        }
      }
      return p2 / s2.length() / n2;
   }
};
main() {
   Solution ob;
   cout << (ob.getMaxRepetitions("acb",4,"ab",2));
}

입력

"acb",4,"ab",2