[LeetCode] Valid Mountain Array

 

 

목차

문제

• 다음 조건을 만족하는지 여부를 체크하는 문제입니다.(산형태가 되어야 함.)
  • 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]
• 예시

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

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

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

• 제약조건
  • 1 <= arr.length <= 104
  • 0 <= arr[i] <= 104

문제 풀이

풀이 1 : One Pass

• 풀이
  • i+1이 n보다 작으면서 arr[i] < arr[i+1] 이면 i를 계속해서 증가시켜 줍니다. (상승)
  • 증가 완료했을 때 i가 0이거나, n-1인 경우에는 증가하는 게 없거나, 끝까지 증가만 하는 경우이므로 산형태가 될 수 없습니다. 따라서 이럴 경우에는 False를 return 합니다.
  • 그 후데 다시 i+1이 n보다 작으면서 arr[i] >arr[i+1]이면 i를 계속해서 증가시켜 줍니다.(하강)
  • 상승과 하강을 모두 마친 결과가 n-1이 아니라면 이는 산형태가 아닌 경우입니다. n-1이라면 산형태이므로 True
• 코드

  • class Solution(object):
        def validMountainArray(self, A):
            N = len(A)
            i = 0
    
            # walk up
            while i+1 < N and A[i] < A[i+1]:
                i += 1
    
            # peak can't be first or last
            if i == 0 or i == N-1:
                return False
    
            # walk down
            while i+1 < N and A[i] > A[i+1]:
                i += 1
    
            return i == N-1

• 시간복잡도
  • O(N)

알게 된 내용

• 문제의 조건을 따랐을 때 결과가 끝까지 도달했다면 문제 조건을 만족하는 것입니다. 이런 식의 풀이 접근도 가능하다는 것을 알게 되었습니다.

출처

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