7. Valid Mountain Array

https://leetcode.com/explore/learn/card/fun-with-arrays/527/searching-for-items-in-an-array/3251/

Explore - LeetCode

문제

주어진 배열이 유효한 마운틴 어레이인 경우 true 반환.

마운틴 어레이에는 요소가 최소 3개 있어야 함.

[0, 3, 2, 1]은 true
반복되는 숫자가 있는 [1, 2, 2, 1]은 false
증가하기만 하는 [1, 2, 3, 4]은 false
감소하기만 하는 [4, 3, 2, 1]은 false

 

내가 해결한 방식

i로 배열 한 칸씩 탐색하면서 i 다음 요소가 커지는지 확인.

i 다음 요소가 작아진 경우, j로 한 칸씩 탐색하면서 다음 요소가 작아지는지 확인.

bool validMountainArray(int* arr, int arrSize){
    int i, j;
    // 길이가 3보다 작으면 마운틴 배열이 아님
    if (arrSize < 3){
        return false;
    }

    // i로는 마지막 앞 칸까지만 확인
    for (i = 0; i < arrSize - 1; i++){
        // 현재 칸보다 다음 칸 숫자가 작은 경우
        if (arr[i] > arr[i+1]){
            // 첫 칸부터 바로 감소하는 경우 
            if (i == 0){
                return false;
            }
            j = i + 1;
            while (j < arrSize-1){
                // 현재 칸이 꼭대기인지 확인(다음 칸은 줄어들기만 하는지 확인)
                if (arr[j] > arr[j+1]){
                    j++;
                } else {
                    return false;
                }
            }
            return true;
        } else if (arr[i] == arr[i+1]){
            // 현재 칸과 다음 칸 숫자가 같은 경우
            return false;
        }
    }
    return false;
}

 

다른 해결 방식(python)

https://leetcode.com/problems/valid-mountain-array/discuss/1717377/JavaC%2B%2BPython-EASY-to-go-through-solution-and-EXPLANATION

left는 0에서 시작. 다음 칸이 현재 칸보다 클 때만 왼쪽에서 오른쪽으로 이동 (->)

right는 끝 인덱스에서 시작. 현재 칸이 이전 칸보다 작을 때만 오른쪽에서 왼쪽으로 이동 (<-)

left와 right가 만나면 mountain array라는 뜻.

만나지 않으면 아니라는 뜻.

def validMountainArray(self, arr: List[int]) -> bool:
    if len(arr) < 3:
        return False

    left = 0
    right = len(arr) - 1
	
    # 마지막 인덱스 앞에서 left가 멈춰야 하므로 left < len(arr) - 2
    # 마지막 인덱스에서 멈추면 [1, 2, 3]같은 배열에서 True를 잘못 반환
    while left < len(arr) - 2 and arr[left] < arr[left + 1]:
        left += 1
	
    # 1번 인덱스에서 right가 멈춰야 하므로 1 < right
    # 0번 인덱스에서 멈추면 [3, 2, 1]같은 배열에서 True를 잘못 반환
    while 1 < right and arr[right] < arr[right - 1]:
        right -= 1

    return left == right