941. Valid Mountain Array

Valid Mountain Array - LeetCode

0보다 같거나 큰 정수로 이루어진 1차원 배열이 주어진다.

주어진 배열이 아래 조건을 만족하는지 참, 거짓을 반환하는 문제다.

조건 설명 그림

조건 1, 입력된 배열은 3보다 같거나 커야 한다.

조건 2, 입력된 배열은 mountain array라고 부르는 조건을 만족해야 한다.

조건 3, mountain array는 배열 안에 유일한 최고점이 있고 최고점을 기준으로 왼쪽, 오른쪽 값이 감소해야 한다(같아도 안된다).

 

1. 풀이

from typing import *


class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:

        if len(arr) < 3:
            return False

        left_peak = 0

        while left_peak < len(arr) - 1 and arr[left_peak] < arr[left_peak + 1]:
            left_peak += 1

        right_peak = len(arr) - 1

        while right_peak > 0 and arr[right_peak - 1] > arr[right_peak]:
            right_peak -= 1

        return 0 < left_peak == right_peak < len(arr) - 1

풀 수 있는 방법이야 많겠지만 최소한의 탐색으로 해결할 수 있도록 풀어보았다.

 

left_peak라는 값은 왼쪽에서 오른쪽으로 탐색하면서 찾는 최고점의 index다.

right_peak라는 값은 오른쪽에서 왼쪽으로 탐색하면서 찾는 최고점의 index다.

탐색 조건을 큰 경우만 전진시킨 뒤, 마지막에 left_peak와 right_peak가 같은지 체크한다.

 

이때 left_peak는 0이 되선 안되고 right_peak는 len(arr)-1이 되어선 안되는데, 그 이유는 left_peak가 0이라는 뜻은 [5,4,3,2,1] 같은 배열이라는 뜻이고 이 배열은 조건에 맞지 않는다. peak가 가리키는 값 5 왼쪽으로 하강하는 값이 없기 때문이다.

right_peak도 마찬가지의 이유로 [1,2,3,4,5] 같은 배열에서 오른쪽으로 하강하는 값이 없기 때문에 조건을 만족하지 못한다.

 

어렵진 않지만 처음에 조건 하나씩 넣어서 풀어보려다가 통과 안되어서 싹 지우고 최대한 예쁘게 풀어보았다.