[JavaScript] leetCode : 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]

배열이 산처럼 오름차순-내림차순으로 이루어져있는지 확인하여 boolean으로 반환하는 문제.
조건은 배열의 길이가 3 이상이어야 하고, 오름차순과 내림차순의 기점이 되는 i의 값이 존재해야 한다.
문제에서 제공해주는 아래 사진을 보면 이해가 더 쉽다.

풀이

const validMountainArray = function(arr) {
 // 배열의 길이가 3보다 작으면 반환한다
  if (arr.length < 3) return false;

  // 좌,우 포인터 하나씩 둔다.
  let left = 0;
  let right = arr.length - 1;

  // 루프 1: 왼쪽부터 오름차순인지 확인
  while (arr[left] < arr[left + 1]) {
      left++;
  }

  // 루프 2: 오른쪽부터 오름차순인지 확인
  while (arr[right] < arr[right - 1]) {
      right--;
  }

  return left === right && left !== 0 && right !== arr.length - 1;

};

포인터를 다양하게 쓸 수 있는 것 같아 정리를 해두려고 한다.

우선 배열의 길이가 3보다 작으면 더이상 진행 되지 않고 false를 반환하도록 했다.

처음엔 중간값을 기준으로 따져보려 했는데 잘 되지 않아서 양쪽 끝에 포인터를 두어서
산처럼 되는지 확인해보기로 했다.

 

왼쪽 포인터는 왼쪽에서부터 오름차순인지,
오른쪽 포인터는 역순으로 가며 오름차순인지 확인하며 부합한다면 인덱스를 더하거나 차감한다.

 

예를 들어 [0,3,4,2,1] 이라는 배열이 있다고 하자.

양 끝에 포인터를 두고 첫번째 while문에 들어가면, 배열의 현재 인덱스 값보다 다음 인덱스의 값이 크다면 포인터는 계속 다음 인덱스로 이동한다. 여기서는 arr[0]인 0보다 arr[1]인 3이 크니 left는 증가할 것이다.

더이상 배열의 다음 인덱스 값이 크지 않은 지점에서 빠져나온다.

산이라면 꼭대기에 해당하는 부분이다.

이어서 두번째 while문은 배열의 마지막 인덱스에서부터 시작한다.

배열의 이전 인덱스 값이 더 크다면 포인터를 감소시켜 이전 인덱스로 향한다.

그럼 두 포인터는 가장 큰 값인 지점에서 만나서 멈추게 된다.

이 때의 left는 2, right도 2.

처음에는 두 포인터의 값이 같을 때만 반환하도록 했는데,

포인터가 움직이지 않은 경우의 테스트케이스가 발생해서 포인터가 초기상태가 아닌 경우를 조건에 포함시켰다.
투포인터의 시간복잡도는 O(n).

 

 

다른 풀이

var validMountainArray = function(arr, edge = 0) {
    for (let i = 1; i < arr.length-1; i++) {
        if (arr[i-1] < arr[i] && arr[i] > arr[i+1]) edge++;
        if (arr[i-1] >= arr[i] && arr[i] <= arr[i+1]) return false;
    }
    return edge == 1;
};

하나의 for문을 통해서 해결했다.
edge라는 초기값이 0인 변수를 지정해줬는데, 가장 꼭대기에 있는 값이 존재하는지 찾는 코드이다.
배열의 인덱스 값을 기준으로 1부터 시작해서 이전 값은 더 작고, 이후값도 작을 때를 찾아 edge를 더해준다.
edge가 존재한다는건 결국 산 모양이 되는 기점값이 있다는 것!

멋진 발상인 것 같다.

 

원문은 아래서 볼 수 있다.

https://leetcode.com/problems/valid-mountain-array/discuss/1717503/Javascript-easy-simple-solution-5-lines-of-code-O(N)-time-O(1)-space