C++로 구현하는 조건을 만족하는 최대 길이 부분배열 찾기

이 튜토리얼에서는 주어진 조건을 만족하는 부분배열(연속된 하위 배열)의 최대 크기를 찾는 프로그램을 다룹니다.

문제 정의

정수로 이루어진 배열이 하나 주어집니다. 목표는 아래 두 조건 중 하나를 만족하는 가장 긴 부분배열의 길이를 구하는 것입니다.

• k가 홀수일 때는 arr[k] > arr[k + 1], k가 짝수일 때는 arr[k] < arr[k + 1]
• k가 짝수일 때는 arr[k] > arr[k + 1], k가 홀수일 때는 arr[k] < arr[k + 1]

쉽게 말해, 인접한 두 요소의 대소 관계가 번갈아 뒤바뀌는(커졌다 작아졌다 하는) 패턴이 유지되는 가장 긴 연속 구간을 찾는 문제입니다. 이러한 배열은 흔히 '터뷸런트(turbulent) 배열'이라고도 불립니다.

예제 코드

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

// a와 b의 대소 관계를 비교하는 함수
int cmp(int a, int b) {
    return (a > b) - (a < b);
}

// 가장 긴 부분배열의 길이를 반환하는 함수
int maxSubarraySize(int arr[], int n) {
    int ans = 1;
    int anchor = 0;
    for (int i = 1; i < n; i++) {
        int c = cmp(arr[i - 1], arr[i]);
        if (c == 0)
            anchor = i;
        else if (i == n - 1 || c * cmp(arr[i], arr[i + 1]) != -1) {
            ans = max(ans, i - anchor + 1);
            anchor = i;
        }
    }
    return ans;
}

int main() {
    int arr[] = {9, 4, 2, 10, 7, 8, 8, 1, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxSubarraySize(arr, n);
}

출력 결과

5

코드 동작 원리

cmp 함수는 두 수를 비교하여 앞의 값이 크면 1, 작으면 -1, 같으면 0을 반환합니다. 이 값을 활용해 인접 요소 사이의 '증가/감소 방향'을 숫자로 표현할 수 있습니다.

maxSubarraySize 함수의 핵심은 앵커(anchor) 기법입니다.

• anchor는 현재 검사 중인 유효한 부분배열의 시작 위치를 나타냅니다.
• 순회 중 두 요소가 같아서 c == 0이 되면 교대 패턴이 깨지므로, 앵커를 현재 위치로 옮겨 새로운 구간을 시작합니다.
• 마지막 요소에 도달했거나, 현재 방향과 다음 방향이 같은 부호(c * cmp(arr[i], arr[i + 1]) != -1)라 방향 전환이 일어나지 않으면 패턴이 종료된 것입니다. 이때 현재 구간의 길이(i - anchor + 1)로 정답을 갱신하고 앵커를 이동합니다.

예제 분석

입력 배열 {9, 4, 2, 10, 7, 8, 8, 1, 9}에서 조건을 만족하는 가장 긴 구간은 [4, 2, 10, 7, 8]입니다. 이 구간은 4>2, 2<10, 10>7, 7<8로 대소 관계가 번갈아 나타나며, 길이는 5입니다. 따라서 출력값은 5가 됩니다.

복잡도

• 시간 복잡도: O(n) — 배열을 한 번만 순회합니다.
• 공간 복잡도: O(1) — 추가적인 메모리를 거의 사용하지 않습니다.