C++로 문자열 끝까지 도달하는 데 필요한 최대 점프 거리 구하기

이 튜토리얼에서는 문자열의 끝에 도달하기 위해 필요한 최대 점프 거리(점프 파워)를 구하는 프로그램을 C++로 작성하는 방법을 알아보겠습니다.

문제 이해하기

문제에서는 '0'과 '1'로만 이루어진 문자열이 주어집니다. 우리가 해야 할 일은 문자열의 앞에서 끝까지 이동할 때 필요한 최대 점프 거리를 계산하는 것입니다.

여기서 중요한 규칙은 다음과 같습니다. 현재 위치의 문자와 같은 문자가 있는 위치로만 점프하여 이동할 수 있습니다. 즉, 마지막 문자와 동일한 문자 사이의 간격 중 가장 큰 값이 곧 최대 점프 거리가 됩니다.

알고리즘 접근 방식

해결 로직은 비교적 간단합니다.

1. 문자열의 마지막 문자를 기준 문자(ch)로 저장합니다.
2. 문자열을 처음부터 순회하면서 기준 문자와 같은 문자를 만날 때마다 그때까지 쌓인 count 값을 확인합니다.
3. count 값이 지금까지의 최댓값(max_so_far)보다 크면 갱신하고, count는 다시 1로 초기화합니다.
4. 순회가 끝나면 max_so_far가 곧 최대 점프 거리입니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;

//최대 점프 거리를 구하는 함수
int powerOfJump(string s) {
   int count = 1;
   int max_so_far = INT_MIN;
   char ch = s[s.length() - 1]; //마지막 문자를 기준으로 설정
   for (int i = 0; i < s.length(); i++) {
      if (s[i] == ch) {
         if (count > max_so_far) {
            max_so_far = count;
         }
         count = 1;
      }
      else
         count++;
   }
   return max_so_far;
}

int main(){
   string st = "1010101";
   cout<<powerOfJump(st);
}

실행 결과

2

동작 원리 설명

예제 문자열 "1010101"의 경우, 마지막 문자는 '1'입니다. 문자열을 순회하면 '1'이 나타나는 위치는 인덱스 0, 2, 4, 6입니다. 각 '1' 사이의 간격은 모두 2이므로, 한 번에 점프할 수 있는 최대 거리는 2가 됩니다.

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.