C++로 주어진 조건을 만족하는 최대 크기의 부분 배열 찾기

이 문제에서는 n개의 정수로 이루어진 배열 arr[]가 주어지며, 주어진 조건을 만족하는 부분 배열(sub-array) 중 가장 큰 크기를 구하는 프로그램을 작성해야 합니다.

문제 설명

아래 두 조건 중 하나를 만족하는 가장 긴 부분 배열의 길이를 찾아야 합니다.

• 부분 배열의 모든 원소에 대해, k가 홀수이면 arr[k] > arr[k+1]이고, k가 짝수이면 arr[k] < arr[k+1]인 경우
• 부분 배열의 모든 원소에 대해, k가 홀수이면 arr[k] < arr[k+1]이고, k가 짝수이면 arr[k] > arr[k+1]인 경우

여기서 k는 부분 배열의 원소가 원본 배열 arr[]에서 가지는 인덱스입니다.

예제로 문제 이해하기

입력

arr[] = {7, 3, 1, 5, 4, 2, 9}

출력

4

설명

부분 배열 {3, 1, 5, 4}는 조건 1을 만족합니다.
k = 1(홀수), arr[k] > arr[k+1], 즉 3 > 1
k = 2(짝수), arr[k] < arr[k+1], 즉 1 < 5
k = 3(홀수), arr[k] > arr[k+1], 즉 5 > 4

해결 접근 방법

예제에서 확인할 수 있듯이, 어떤 조건이든 참이 되려면 부분 배열의 원소들이 크다-작다 패턴으로 번갈아 나타나야 합니다. 즉, 첫 번째 원소가 두 번째 원소보다 크다면, 두 번째 원소는 세 번째 원소보다 작아야 하며, 이런 식으로 계속 교대로 반복되어야 합니다.

계산을 쉽게 하기 위해 인접한 두 원소 사이의 대소 관계를 저장하는 관계 배열(relArr)을 만들 수 있습니다. 관계 배열은 다음과 같이 정의됩니다.

arr[i] == arr[i + 1] 이면, relArr[i] = 'E'
arr[i] > arr[i + 1] 이면, relArr[i] = 'G'
arr[i] < arr[i + 1] 이면, relArr[i] = 'S'

이 배열을 활용하면 최대 부분 배열의 크기를 손쉽게 구할 수 있습니다. 조건을 만족하는 부분 배열은 'G'와 'S'가 번갈아 나타나는 형태여야 합니다.

구현 예제

다음은 위 해결 방법의 동작을 보여주는 C++ 프로그램입니다.

#include<iostream>
using namespace std;

char findRel(int a, int b) {
    if(a > b)
        return 'G';
    else if(a < b)
        return 'S';
    return 'E';
}

int calcMaxSubArray(int arr[], int n) {
    int maxLen = 1;
    int len = 1;
    char c = findRel(arr[0], arr[1]);
    for(int i = 1; i <= n-1; i++){
        if(c == 'S' && findRel(arr[i], arr[i + 1]) == 'G')
            len++;
        else if(c == 'G' && findRel(arr[i], arr[i + 1]) == 'S')
            len++;
        else {
            if(maxLen < (len + 1))
                maxLen = (len + 1);
            len = 1;
        }
        c = findRel(arr[i], arr[i+1]);
    }
    return maxLen;
}

int main() {
    int arr[] = {7, 3, 1, 5, 4, 2, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"주어진 조건을 만족하는 부분 배열의 최대 크기는 "
        <<calcMaxSubArray(arr, n);
}

출력 결과

주어진 조건을 만족하는 부분 배열의 최대 크기는 4

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