Valid Mountain Array

문제

전제
정수형 배열이 arr이 주어질때 arr의 배열 형태가 산 모양과 같은지 체크해라.

산 모양은 arr[0]<arr[1]<.....>arr[arr.length-2]>arr[arr.length-1] 처럼
ㅅ 모양과 같다.

arr.length >= 3이다.

예제1

입력: arr = [2,1]
출력: false
설명 : 배열의 길이가 3보다 작다.

예제2

입력: arr = [3,5,5]
출력: false
설명 : 배열에 같은 요소가 있으면 안된다.

예제3

입력: arr = [0,3,2,1]
출력: true

제약 조건

1 <= arr.length <= 104
0 <= arr[i] <= 104

---

Solution

class Solution {
      public boolean validMountainArray(int[] arr) {
	  	int right = arr.length - 1;
      	int left = 0;
      	boolean result = true;
		
        if(arr.length >= 3 && (arr[left] < arr[left+1] && arr[right] < arr[right-1])) {
        	for(int i = 0; i < arr.length; i++) {
            	if(i+1 < arr.length && (arr[i] > arr[i+1] || arr[i] == arr[i+1])) {
            		for(int j = i; j < arr.length; j++) {
                		if(j+1 < arr.length && (arr[j] < arr[j+1] || arr[j] == arr[j+1])) {
						return false;
                        }
					}
				}
			}
			result = true;
		}else {
			return false;
		}
        return result;
	}
}

먼저 첫 if조건에서
배열의 길이가 2보다 큰 것과
배열의 0과 0+1이 "<"의 관계인지 arr.length -1 과 arr.length -2가 ">"의 관계인지를
함께 검증했다.

첫 if 조건을 만족한다면 0 <= i < arr.length의 크기 만큼 배열을 반복 조회 할 것이다.
첫 i반복문 안의 if 조건은 배열의 관계 모양이 ">"이거나 "=="면 이중반복을 시작한다.

i <= j < arr.length의 그키 만큼 배열을 반복 조회 한다
이 이중 반복의 if조건은 배열의 관계 모양이 "<"이거나 "=="이면 false를 리턴한다.

이미 첫 반복문에서 배열의 관계 모양이 ">"로 변환되는 요소부터 이중 반복을 시작하기 때문에
관계 모양이 ">"로 지속되어야 한다.
하지만 중간에 "<"이거나 "=="이 발생하면 ㅅ모양이 아니기때문에 false를 리턴한다.

로직이 너무 거창하고 이중반복으로 속도 또한 비효율적이다.

반복을 한 번만 진행했다.

그래서 반복을 한 번만 진행했다.

class Solution {
	public boolean validMountainArray(int[] arr) {
		int right = arr.length - 1;
		int left = 0;
		boolean result = false;

		if (arr.length >= 3 && (arr[left] < arr[left + 1] && arr[right] < arr[right - 1])) {
			for (int i = 0; i < arr.length - 1; i++) {		
				if (!result && arr[i+1] < arr[i]) {
					result = true;
				}
				if ((result && (arr[i] < arr[i+1])) || (arr[i] == arr[i + 1])) {
					return false;
				}
			}
		} else {
			return false;
		}
        return result;
	}
}

첫 if 조건은 처음 작성한 solution과 같다.
이때 i반복문 하나만을 이용해서 result가 true일때(관계 부호가 ">"인 경우)
관계부호가 "<"이거나 "=="이면 false를 리턴한다.

설명 하기도 간단해졌고 훨씬 빠르게 실행되었다.

하지만 아쉽게도 가장 빠르진 않았다.

가장 빠른 solution

class Solution {
    public boolean validMountainArray(int[] arr) {
        int i = 0, n = arr.length;
        //strictly increasing
        while(i+1 < n && arr[i] < arr[i+1]){
            i++;
        } 
        //peak can not be first or last
        if(i==0 || i==n-1){
            return false;
        }
        //strictly decreasing
        while(i+1 < n && arr[i] > arr[i+1]){
            i++;
        } 
        
        //true if i reaches till end.
        return i==n-1;
    }
}

대단하다