[LeetCode] 978. Longest Turbulent Subarray

문제 출처: https://leetcode.com/problems/longest-turbulent-subarray/

Longest Turbulent Subarray - LeetCode

---

문제

정수 배열 arr에서 격동(turbulent) 하위 배열 중 가장 큰 크기를 반환하라.

 

하위 배열이 격동(turbulent)하다는 것은 각 인접 원소 쌍의 비교 부호가 뒤집히는 것을 말한다.

 

더 형식적으로 표현하면, 하위 배열 $[arr[i], arr[i+1], ..., arr[j]]$이 다음과 같다면 격동적이라고 말한다:

• $i \leq k < j$
  • k가 홀수 일 때, $arr[k] > arr[k+1]$ 이고
  • k가 짝수 일 때, $arr[k] < arr[k+1]$
• 또는, $i \leq k < j$
  • k가 홀수 일 때, $arr[k] < arr[k+1]$ 이고
  • k가 짝수 일 때, $arr[k] > arr[k+1]$

예제

Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5

Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

Input: arr = [4,8,12,16]
Output: 2

Input: arr = [100]
Output: 1

---

풀이

투 포인터 접근 방식을 사용하여 문제를 풀 수 있습니다.

우리가 어떠한 방식으로든 탐색을 통해 빨간 범위의 하위 배열이 turbulent 하다는 것을 알았다고 한다면, 그 내부의 어떤 지점에서든 동일한 위치에서 turbulent가 이어지지 못할 것입니다.

 

그래서 새로운 turbulent 하위 배열을 찾기 위해서는 아래의 그림과 같이 파란색 지점부터 새롭게 탐색을 시작해야 합니다.

이러한 과정을 투 포인터 알고리즘을 이용하여 두 개의 포인터 지점을 이동시켜가며 최대 turbulent 하위 배열의 크기를 찾는 것입니다.

 

코드를 통해 구체적인 방식을 살펴보면,

var maxTurbulenceSize = function(arr) {
    let answer = 1;
    
    if (arr.length < 2) { return answer; }
    
    let left = 0;
    let preValCompare = 0;
    for (let right = 0; right < arr.length-1; right++) {
        const nextValCompare = arr[right] - arr[right+1];
        answer = Math.max(answer, right - left +1);
        
        // left를 움직여야 하는 케이스
        if (nextValCompare == 0) {
            left = right + 1;
        } else if (preValCompare > 0 && nextValCompare > 0) {
            left = right;
        } else if (preValCompare < 0 && nextValCompare < 0) {
            left = right;
        }
        
        preValCompare = nextValCompare;
    }
    answer = Math.max(answer, arr.length - left)
    
    return answer;
};

left와 right의 두 개의 포인터 역할을 할 변수를 설정하고, 각각 left는 turbulent 하위 배열의 시작 지점을 가리키는 것이고, right는 turbulent 하위 배열의 끝을 가리키도록 유지합니다.

 

turbulent 배열의 조건을  $odd+1 = even$ 이고 $even+1 = odd$ 이라는 것을 이용하여 다음과 같이 재정의 할 수 있습니다.

• $i \leq k < j$:
  • $arr[k-1] < arr[k]$ 이고, $arr[k] > arr[k+1]$
    ( = $arr[k-1] - arr[k] < 0$ 이고, $arr[k] - arr[k+1] > 0$ )
  • $arr[k-1] > arr[k]$ 이고, $arr[k] < arr[k+1]$
    ( = $arr[k-1] - arr[k] > 0$ 이고, $arr[k] - arr[k+1] < 0$ )

 

위 조건에 따라 right+1 위치를 turbulent 하위 배열에 추가해도 되는지 $arr[right-1] - arr[right]$와 $arr[right] - arr[right+1]$의 부호 비교를 통해 판단할 수 있습니다.

• 부호가 다르다면, right+1은 포함 가능. left는 현재 위치 그대로를 유지
• 부호가 같다면, right+1은 포함 불가능. left를 현재 right 위치로 이동

 

위 두 케이스에 추가적으로 $arr[right] - arr[right+1] = 0$인 케이스를 생각해봐야 합니다.

 

이 케이스는 $arr[right] = arr[right+1]$를 의미하고, 이는 left를 right 위치로 옮겨도 right와 right+1의 관계가 turbulent하지 못합니다. 이에 left를 right+1 위치로 이동시켜야 합니다.

 

이러한 일련의 과정들을 right가 배열의 끝에 다다를 때까지 반복합니다.

 

Github: 978.js

GitHub - opwe37/Algorithm-Study