C++에서 첫 번째 요소와 마지막 요소가 같은 부분 배열의 최대 길이 구하는 방법

문제 개요

이 문제에서는 문자 배열이 주어집니다. 우리가 작성해야 할 프로그램은 첫 번째 요소와 마지막 요소가 서로 동일한 부분 배열(subarray)의 최대 길이를 출력하는 것입니다.

예시로 문제 이해하기

입력 − array = {'t', 'u', 't', 'o', 'r', 'i', 'a', 'l', 's', 'p', 'o', 'i', 'n', 't'}

출력 − 14

설명 −

부분 배열 {'t', 'u', 't', 'o', 'r', 'i', 'a', 'l', 's', 'p', 'o', 'i', 'n', 't'}는 't'로 시작하고 't'로 끝나므로 조건을 만족하며, 그 길이는 14입니다.

접근 방법

이 문제를 해결하려면 배열 속 각 문자가 처음 등장하는 위치(first occurrence)와 마지막으로 등장하는 위치(last occurrence)를 찾은 뒤, 다음 공식을 적용합니다.

부분 배열의 길이 = 마지막 등장 위치 − 첫 번째 등장 위치 + 1

모든 문자에 대해 계산한 결과 중 가장 큰 값이 곧 최대 길이가 됩니다.

예제 풀이

배열 = {a, b, a, c, b, a}

• 문자 'a': 첫 번째 등장 인덱스 0, 마지막 등장 인덱스 5
  → 부분 배열 길이 = 5 − 0 + 1 = 6, 최대 길이(maxLength) = 6
• 문자 'b': 첫 번째 등장 인덱스 1, 마지막 등장 인덱스 4
  → 부분 배열 길이 = 4 − 1 + 1 = 4, 최대 길이는 그대로 6 유지

C++ 구현 예제

첫 번째 요소와 마지막 요소가 같은 부분 배열의 최대 길이를 출력하는 프로그램 −

#include <iostream>
using namespace std;
int maxSubArrLength(string arr, int n){
    int firstOccurrence, lastOccurrence = -1;
    int maxlength = 0;
    char ch;
    for (int i = 0; i < n; i++){
        ch = arr[i];
        firstOccurrence = lastOccurrence = i;
        for(int j = i; j<n; j++){
            if(arr[j] == ch)
                lastOccurrence = j;
        }
        maxlength = max(maxlength, (lastOccurrence - firstOccurrence + 1));
    }
    return maxlength;
}
int main(){
    string arr = "tutorialsPoint";
    int n = arr.length();
    cout<<"첫 번째 요소와 마지막 요소가 같은 부분 배열의 최대 길이는 "<<maxSubArrLength(arr, n);
    return 0;
}

실행 결과

첫 번째 요소와 마지막 요소가 같은 부분 배열의 최대 길이는 14

복잡도 분석 및 최적화 아이디어

위 구현은 각 문자마다 배열 전체를 다시 훑으므로 시간 복잡도는 O(n²)이며, 추가 메모리를 거의 사용하지 않아 공간 복잡도는 O(1)입니다.

성능을 개선하려면 각 문자의 첫 등장 위치를 해시 맵(unordered_map)에 저장해 두면 됩니다. 이렇게 하면 배열을 한 번만 순회(O(n))하면서도 현재 인덱스와 해당 문자의 첫 등장 위치 차이만으로 최대 길이를 갱신할 수 있어, 입력 크기가 클 때 훨씬 효율적입니다.