난류 부분 배열(Turbulent Subarray)이란?
배열 A의 부분 배열 A[i], A[i+1], ..., A[j]가 다음 조건 중 하나를 만족할 때, 이를 "난류(turbulent)" 상태라고 정의합니다.
i <= k < j인 모든k에 대해,k가 홀수일 때는A[k] > A[k+1],k가 짝수일 때는A[k] < A[k+1]- 반대로 같은 범위의 모든
k에 대해,k가 짝수일 때는A[k] > A[k+1],k가 홀수일 때는A[k] < A[k+1]
쉽게 말해, 부분 배열 안에서 인접한 두 원소를 비교하는 부등호 방향이 매번 번갈아 뒤집히면 그 부분 배열은 난류 상태입니다. 우리의 목표는 배열 A에서 이런 난류 부분 배열 중 가장 긴 것의 길이를 찾는 것입니다.
문제 예시
입력이 [9,4,2,10,7,8,8,1,9]라면 정답은 5입니다. A[1] > A[2] < A[3] > A[4] < A[5], 즉 4 → 2 → 10 → 7 → 8처럼 부등호가 교차하는 구간의 길이가 5이기 때문입니다.
알고리즘 접근 방법: 동적 계획법
이 문제는 동적 계획법(DP)을 활용하면 O(n) 시간에 해결할 수 있습니다. 핵심 아이디어는 "현재 위치에서 끝나는 난류 부분 배열"을 두 가지 상태로 나누어 추적하는 것입니다.
- currBig: 현재 위치에서 끝나고, 마지막 비교에서 현재 원소가 이전 원소보다 큰(A[i] > A[i-1]) 난류 부분 배열의 최대 길이
- currSmall: 현재 위치에서 끝나고, 마지막 비교에서 현재 원소가 이전 원소보다 작은(A[i] < A[i-1]) 난류 부분 배열의 최대 길이
부등호가 번갈아 나타나야 하므로, 지금 "커짐"으로 끝나려면 바로 이전 단계는 반드시 "작아짐"으로 끝났어야 합니다. 이 관계가 곧 점화식이 됩니다. 전체 과정은 다음과 같습니다.
- n := 배열 A의 크기
- prevBig := 1, prevSmall := 1, currBig := 1, currSmall := 1, ret := 1로 초기화
- i를 1부터 n-1까지 반복:
- A[i] > A[i-1]이면 currBig := 1 + prevSmall
- A[i] < A[i-1]이면 currSmall := 1 + prevBig
- ret := max(ret, currBig, currSmall)
- prevSmall := currSmall, prevBig := currBig으로 갱신한 뒤 currSmall := 1, currBig := 1로 초기화
- ret 반환
참고로 A[i]와 A[i-1]이 서로 같으면 어떤 조건도 성립하지 않아 두 길이가 모두 1로 되돌아갑니다. 즉, 같은 값이 연속되는 순간 기존 난류 구간이 끊기고 새로운 구간이 시작됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxTurbulenceSize(vector<int>& A) {
int n = A.size();
int prevBig = 1;
int prevSmall = 1;
int currBig = 1;
int currSmall = 1;
int ret = 1;
for(int i = 1; i < n; i++){
if(A[i] > A[i - 1]){
currBig = 1 + prevSmall;
}
if(A[i] < A[i - 1]){
currSmall = 1 + prevBig;
}
ret = max({ret, currBig, currSmall});
prevSmall = currSmall;
prevBig = currBig;
currSmall = 1;
currBig = 1;
}
return ret;
}
};
int main(){
vector<int> v1 = {9,4,2,10,7,8,8,1,9};
Solution ob;
cout << (ob.maxTurbulenceSize(v1));
}
입력
[9,4,2,10,7,8,8,1,9]
출력
5
이 구현은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 상수 개수의 변수만 사용하므로 공간 복잡도는 O(1)입니다.