[Array] Valid Mountain Array

Given an array of integers arr, return true if and only if it is a valid mountain array.

Recall that arr is a mountain array if and only if:

• arr.length >= 3
• There exists some i with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

 

문제의 친절한 그림을 보면, valid mountain은 Increasing과 Decreasing의 변화가 단 한번만 일어나는 배열은 뜻하는 것 같다.(물론 mountain이니까 Inceasing이 먼저다)

즉, 주어진 배열의 각 원소 크기가 증가하다가 감소하는지를 묻고 있다.

 

해결 전략은 다음과 같았다

 

1) 일단 경계값들을 제외한다.

이 문제의 경우 '배열의 크기가 3보다 작다'거나 '배열이 처음부터 감소한다'는 경우에 속한다.

경계값에 해당하는 경우 바로 false를 리턴.

 

2)그 외에 같은 값의 원소가 연속되어 있는 경우도 false case이다. 

이 조건은 Loop를 돌며 건져내도록 뒤로 미뤄두자.

 

3) 극대점에 도달했는지 여부를 변수로 둔다. 아래 코드의 경우 peakReached로 설정. 디폴트는 false다.

 

4) 배열에 대한 Loop를 돈다. 

만약 연속된 같은 값이 있다면 바로 false 리턴.

연속된 두 원소에 대해, 이전원소가 다음원소보다 커지는 순간 peakReached를 true로 설정한다.

 

5) peakReached가 true로 변하기 전까지는, 이 배열의 원소크기는 계속 증가해야 한다.

true로 변한 후에는, 배열의 원소크기가 계속 감소해야 한다.

 

따라서 peakReached가 false인 경우, 이전배열이 다음배열보다 크다는 조건이 true인 경우

peakReached가 true인 경우, 이전배열이 다음배열보다 크다는 조건이 false인 경우는

valid mountain이 아니므로 false를 리턴한다.

 

6) 앞선 모든조건에 해당이 없다면 true를 리턴한다.  

 

var validMountainArray = function(arr) {

    if (arr.length < 3) return false

    if (arr[0] > arr[1]) return false

//경계값 제외

    let peakReached = false

//peak에 도달했는지 여부를 boolean으로 설정

    for (let index = 1; index < arr.length; index++) {

        if (arr[index - 1] === arr[index]) return false

//연속된 원소의 크기가 같은 경우 바로 false

        if (arr[index - 1] > arr[index]) peakReached = true

//peak에 도달한 경우 peakReached가 true로 변경

        if (arr[index - 1] < arr[index] === peakReached) return false

//peak도달전에는 조건이 false, 도달후에는 조건이 true인 경우에 false리턴

    }

    return peakReached

//모든 조건을 통과하면 true 리턴

};