[LeetCode] 845. Longest Mountain in Array

출처: https://leetcode.com/problems/longest-mountain-in-array/

Longest Mountain in Array - LeetCode

문제

배열 arr이 다음과 같을 때 산 배열이라 할 수 있다:

• arr.length >= 3
• 0 < i < arr.length-1 에서 인덱스 i가 존재한다
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

정수 배열 arr에서 가장 긴 서브배열(산)의 길이 를 반환하라. 산 서브배열이 없다면 0을 반환하라.

예제

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Input: arr = [2,2,2]
Output: 0
Explanation: There is no mountain.

풀이

산을 구성하는 서브배열을 찾기 위해서 상승 경사와 하강경사를 찾아야 할 것이다. 그리고 하강경사는 상승경사 바로 다음에 이어서 나오는 부분이어야 할 것이다.

 

배열에서 상승 경사를 어떻게 찾을 수 있을까. arr[i] < arr[i+1]로 순간의 상승 여부를 체크할 수 있을 것이고 이를 반복하면 상승 경사를 찾을 수 있을 것이다. 코드로 정리하면 다음과 같다.

const n = arr.length
let base = 0;
while (base < n) {
    i = base;
    if (i < n-1 && arr[i] < arr[i+1]) {
        while (i < n-1 && arr[i] < arr[i+1]) i += 1;
    }
    base = i + 1;
}

이제 하강 경사를 찾아야 할 것이다. 하강 경사는 상승 경사 바로 다음에 이어 나와야 한다. 그렇기 때문에 상승 경사의 끝이 i라면, arr[i] > arr[i+1]를 바로 체크하여 하강 경사가 나오는지 확인하고, 하강 경사라면 어디까지가 하강 경사인지 체크해야 한다. 방식은 상승 경사를 찾는 것과 같다.

const n = arr.length
let base = 0;
while (base < n) {
    i = base;
    if (i < n-1 && arr[i] < arr[i+1]) {                        // ------------- 1
        while (i < n-1 && arr[i] < arr[i+1]) i += 1;

        if (i < n-1 && arr[i] > arr[i+1]) {                    // ------------- 2
            while (i < n-1 && arr[i] > arr[i+1]) i += 1;
            mountain_length = i - base + 1;
        }
    }
    base = Math.max(i, base+1);                                // ------------- 3
}

base를 업데이트하는 부분을 보면, 첫 코드와 두 번째 코드가 다르다. 상승 경사만을 구할 때는 i+1이지만 하강 경사까지 구할 때는 Math.max(i, base + 1)이다.

위 그림을 보자. 상승 경사에서 i는 그림과 같이 상승 경사의 끝 지점을 가르키게 된다. 그렇기에 다음 상승경사의 시작점의 후보는 i+1이 될 것이다. 만약 첫 코드에서 i로 업데이트 했다면 arr[i] < arr[i+1]조건에 걸려 base가 제대로 업데이트되지 않아 무한 반복에 빠지게 된다.

 

반면 하강 경사 탐색을 포함하는 두번 째 코드에서 i+1로 업데이트를 하게 되면 찾아지는 상승 경사에서 i지점이 제외가 되는 상황이 발생한다.

 

코드와 연관 지어 생각해면 ③에 도달하는 경로는 3가지가 있고 각기 다음과 같이 base를 업데이트시킨다.

• 조건문 ①에 진입하지 못하는 경우 => base+1로 업데이트
• 조건문 ①에 진입했지만, ② 조건문에는 진입하지 못하는 경우 => i로 업데이트
• 조건문 ②에 진입한 경우 => i로 업데이트

기본적으로 ①에 진입하는 순간 i는 base보다 커지기 때문에 대부분의 경우 ③에서 i가 선택된다. 이후에 찾아지는 상승 경사의 시작 위치를 제대로 찾기 위함이다.

 

문제는 조건문 ①에 진입했지만, ② 조건문에는 진입하지 못하는 경우에서 i로 업데이트하는 것은 위에서 살펴본 무한 반복에 빠지게 하는 흐름과 비슷하다. 하지만, 여기서는 Math.max(i, base + 1)에 의해 base + 1이 선택되면서 무한반복에 빠지지 않도록 한다.

 

github: 845.js

opwe37/Algorithm-Study