[Leetcode/941] Valid Mountain Array 문제 번역/풀이

문제 바로가기 문제 풀이 모음집

🔥 문제

정수 배열 arr가 주어지고 이 배열이 산 모양 배열일 때 true를 반환하여라.

배열이 산 모양 배열이라는 것은 다음의 경우에만 해당된다.

• arr.length >= 3
• 아래 조건을 만족하는 i(0 < i < arr.length - 1)가 존재한다.
  • arr[0] < arr[1] < … < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > … > arr[arr.length - 1]

배열의 어느 원소를 기점으로 좌측은 상승하는 구간, 우측은 하강하는 구간이어야한다. 상승하는 구간과 하강하는 구간이 각각 1번씩 반드시 존재해야한다.

🔥 풀이

풀이1: 나의 풀이

index 0부터 배열끝까지 한 방향으로 탐색해나간다. 현재 값이 이전 값보다 크면 상승구간, 작으면 하강구간이 된다.

중간에 탐색을 멈출 조건은 3가지가 있다.

1. 평평한 구간(현재 값 = 이전 값)
2. 상승구간 없이 하강구간
3. 이미 하강구간 지났는데 다시 상승구간

이 경우를 제외하고는 배열 끝까지 탐색을 하고, 마지막에 상승구간과 하강구간이 둘 다 존재했을 경우에만 true를 반환한다.

class Solution {
    public boolean validMountainArray(int[] arr) {
        if (arr == null || arr.length < 3) {
            return false;
        }
        int previous = arr[0];
        boolean uphill = false;
        boolean downhill = false;
        for (int i = 1 ; i < arr.length ; i++) {
            int current = arr[i];
            if (current == previous || (!uphill && current < previous) || (downhill && current > previous)) {
                return false;
            } else if (!downhill && current > previous) {
                uphill = true;
            } else if (uphill && current < previous) {
                downhill = true;
            }
            previous = current;
        }
        return uphill && downhill;
    }
}

Runtime: 5ms
Memory Usage: 51.5MB

풀이2: 다른 사람 풀이

hi-malik님의 풀이를 가져와봤다.

배열을 탐색할 변수를 두 개 선언한다.

• left: index 0부터 시작해서 n-1방향으로 진행한다.
• right: index n-1부터 시작해서 0방향으로 진행한다.

left는 상승구간일 경우에 left++하고, right은 하강구간일 경우에 right--한다. 마지막에 결국 left == right이면 산의 정상이 딱 하나 존재했다는 의미가 되므로 true를 반환한다.

class Solution {
    public boolean validMountainArray(int[] arr) {
        if(arr.length < 3) return false;
        int left = 0;
        int right = arr.length - 1;
        while(left + 1 < arr.length - 1 && arr[left] < arr[left + 1]) left++;
        while(right - 1 > 0 && arr[right] < arr[right - 1]) right--;
        return left == right;
    }
}

Runtime: 3ms
Memory Usage: 51.7MB