[LeetCode] 941. Valid Mountain Array

문제 출처: https://leetcode.com/problems/valid-mountain-array/

Valid Mountain Array - LeetCode

문제

정수 배열 arr이 유효한 산 배열이라면 true를 반환하라.

 

배열이 다음과 같다면, 산 배열이다:

• arr.length >= 3
• 0 < i < arr.length-1에서 아래와 같은 i가 있다.
  • arr[0] < arr[1] < ... < arr[i-1] < arr[i]
  • a[i] > arr[i+1] > ... > arr[arr.length-1]

예제

Input: arr = [2,1]
Output: false

Input: arr = [3,5,5]
Output: false

Input: arr = [0,3,2,1]
Output: true

풀이

문제에 주어진 산의 조건을 토대로 배열을 1) 오르막 2) 정상 3) 내리막 으로 나눌 수 있다.

 

오르막과 내리막은 강한 증가와 강한 감소가 이루어지는지 체크를 통해 확인할 수 있다.

if (arr[0] < arr[1]) {
    let i = 0;
    // 오르막
    while (i+1 < arr.length && arr[i] < arr[i+1]) { i += 1; }
    if (arr[i] == arr[i+1]) { return false }

    // 내리막
    while (i+1 < arr.length && arr[i] > arr[i+1]) { i += 1; }
    if (i != arr.length-1) { return false }
}

각각 while구문 다음의 조건문을 통해, while문의 종료가 어떤 조건에 의해 이루어졌는지 체크를 한다.

 

오르막의 경우, 만약 arr[i] > arr[i+1]이면 내리막 체크를 통해 산 여부를 체크해야 하지만, arr[i] == arr[i+1]이면 내리막 체크와는 별개로 강한 증가가 아니기 때문에 산이 아니라고 판별할 수 있다.

 

내리막의 경우도 배열이 올바른 산의 형태라면 한번의 내리막을 통해 배열의 끝 지점에 도달할 수 있어야한다. 그렇지 않다면 주어진 배열은 찾고자 하는 산이 아니라 판별해야 한다.

 

이제 정상에 대해서 생각해보자. 정상의 위치를 p라고 하면 p는 오르막의 끝지점이면서 내리막의 시작지점이여야 하고 0 < p < arr.length범위를 가져야한다.

 

첫 조건은 오르막에 대한 while문 이후의 조건문에 의해 판별이 되기 때문에 고려를 하지 않아도 된다. 하지만 두번째 조건은 한번 확인해야 할 필요가 있다.

 

이를 코드로 작성하면 아래와 같다.

if (arr[0] < arr[1]) {
    let i = 0;
    // 오르막
    while (i+1 < arr.length && arr[i] < arr[i+1]) { i += 1; }
    if (arr[i] == arr[i+1]) { return false }

    // 정상 위치 체크
    if (i == 0 || i == arr.length-1) { return false }

    // 내리막
    while (i+1 < arr.length && arr[i] > arr[i+1]) { i += 1; }
    if (i != arr.length-1) { return false }
}

Github: 941.js

opwe37/Algorithm-Study