[LeetCode] Valid Mountain Array

Question

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]

위 사진처럼 strictly increasing 하고 strictly decreasing 하면 True, 아니면 False를 반환하는 문제였다.
산은 (내리막이 아닌) 오르막부터 시작해야하며 중간에 높이 변화 없이 머물러 있으면 안된다.

Example

Input: arr = [2,1]
Output: false

Input: arr = [3,5,5]
Output: false

Input: arr = [0,3,2,1]
Output: true

Constraints

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^4

Solution 1

class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        
        gap=[]
        tmp=[] # gap에서 첫번째 음수 이후 마지막까지 slice
        flag=0 # gap에서 첫번째 음수 판별 위해
        
        plus_cnt=0 # 리스트 요소가 모두 양수인지 판별 위해
        minus_cnt=0 # 리스트 요소가 모두 음수인지 판별 위해
        
        if len(arr)<3:
            return False
        else:
            for i in range(len(arr)-1):
                gap.append(arr[i+1]-arr[i]) # 차이
           
            for x in gap:
                if x==0: # gap이 0인 곳이 있으면 False
                    return False
                elif x>0: # gap이 모두 양수 혹은 모두 음수인지 판별하기 위해
                    plus_cnt+=1
                else: # x<0이면
                    minus_cnt+=1
            # gap이 모두 양수 혹은 모두 음수이면 False
            if plus_cnt==len(gap) or minus_cnt==len(gap):
                return False
            
            for i,x in enumerate(gap):
                if x<0 and flag==0: # gap이 처음으로 음수
                    flag=1
                    for k in range(i,len(gap)):
                        tmp.append(gap[k])
            # 한번 음수로 바뀌면 그 뒤로는 쭉 내리막(음수)이어야 함
            for x in tmp:
                if x>0:
                    return False
                
            return True
        
    # 중복이 있으면 True, 없으면 False 반환하는 함수 (사용 안함)
    # def hasDuplicates(self, arr: List[int]) -> bool:
    #     return len(arr)!=len(set(arr)) 

• 직접 푼 풀이이다.
• gap은 리스트 요소와 요소 사이의 높이 차이를 담은 리스트이다.
• 모든 테스트 케이스를 통과하기 위해서는 gap의 여러가지 조건에 대해 잘 생각해야한다.

  gap의 조건

  • gap의 요소 중 0이 있으면 안된다. (중간에 높이 변화 없이 머무르는 것)
  • gap의 요소가 전부 양수이거나 음수이면 안된다. (오르막 혹은 내리막으로만 이루어진 것)
  • gap에서 처음으로 음수가 나온 이후부터는 무조건 마지막까지 계속해서 음수가 나와야 한다. (내리막 구간에서 다시 올라가는 것)

Solution 2

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

        i=1
        while i<len(arr) and arr[i]>arr[i-1]: # 오르막 구간
            i+=1

        if i==1 or i==len(arr): # 계속 오르막이거나 계속 내리막이면 False
            return False

        while i<len(arr) and arr[i]<arr[i-1]: # 내리막 구간
            i+=1

        return i==len(arr) # i와 len(arr)가 같으면 True, 다르면 False

• 다른 분의 풀이이다.
• 이 풀이가 런타임이 더 작다.

끄적

• 통과는 하였지만 여러가지 테스트 케이스를 고려하느라 시간이 많이 걸린 문제였다..

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기