[LeetCode] 845. Longest Mountain in Array
출처: https://leetcode.com/problems/longest-mountain-in-array/
Longest Mountain in Array - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제
배열 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
Contribute to opwe37/Algorithm-Study development by creating an account on GitHub.
github.com