[리트코드 LeetCode] Find Peak Element (Python)

Find Peak Element

• https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/801/
• 분류: Top Interview Questions - Medium - Sorting and Searching

Explore - LeetCode

문제

• peak element는 그 주변의 원소들보다 큰(strictly greater) 원소다.
• 주어진 0-indexed 정수 배열 nums의 peak element를 찾고 그 인덱스를 반환하라. 만약 peak가 여러 개라면, 아무 peak의 인덱스나 반환하라.
• nums[-1] = nums[n] = -∞으로 가정하라. 즉, 원소는 배열 밖의 인접한 원소들보다 항상 크다고 생각하라.
• O(logn) 시간 복잡도로 작동하는 알고리즘을 작성하라.
• type nums: List[int] / rtype: int

예시

Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

조건

• 1 <= nums.length <= 1000
• -2^31 <= nums[i] <= 2^31 - 1
• nums[i] != nums[i + 1] for all valid i. (인접한 원소와 항상 값이 다르다)

풀이

1. 선형 탐색

: for문으로 주어진 원소에 대해 인접한 원소가 자기보다 작은지 비교하고 첫번째 peak를 만나면 그 인덱스를 반환

 

boundary 원소에 대한 연산

• 마지막 원소가 마지막-1 원소보다 크기만 해도 peak → 마지막 원소 인덱스(n-1) 반환
• 첫번째 원소가 두번째 원소보다 크기만 해도 peak → 0 반환

class Solution(object):
    def findPeakElement(self, nums):
        n = len(nums)
        if n == 1 or nums[0] > nums[1]:
            return 0
        if nums[-1] > nums[-2]:
            return n - 1
        for i in range(1, n-1):
            if nums[i-1] < nums[i] and nums[i] > nums[i+1]:
                return i

Time: O(n) / Space: O(1)

Runtime: 31 ms (beats 51.49%) / Memory Usage: 13.4 MB (beats 93.02%)

 

더 빠르게 처리하기 위한 방법: peak 성질을 활용

• boundary if문을 통과했다는 것은 원소 값이 계속 증가하는 상황 - 원소 값이 감소하는 지점을 찾아 그 직전의 인덱스 반환 (while문 이용)
• peak라는 것은 계속 증가하다가 다음 원소가 나보다 작은 것

class Solution(object):
    def findPeakElement(self, nums):
        if len(nums) == 1 or nums[0] > nums[1]:
            return 0
        if nums[-1] > nums[-2]:
            return len(nums) - 1
        idx = 0
        while nums[idx] < nums[idx+1]:
            idx += 1
        return idx

Time: O(n) / Space: O(1)

Runtime: 20 ms (beats 97.03%) / Memory Usage: 13.6 MB (beats 48.74%)

 

같은 아이디어로 for문으로 peak 찾기

class Solution(object):
    def findPeakElement(self, nums):
	    for i in range(1, len(nums)):
				if nums[i] < nums[i-1]:
					return i-1
			return len(nums)-1

Time: O(n) / Space: O(1)

Runtime: 36 ms (beats 13.16%) / Memory Usage: 13.4 MB (beats 93.02%)

 

2. 이분 탐색

시간 복잡도 O(log n)으로 해결하라는 조건을 보면 바로 이분 탐색이 생각날 것이다.

문제는 이것을 어떻게 적용하느냐 인데 아이디어는 이렇다.

 

0~n-1 탐색 시작

low ≤ high인 동안

(1) 만약 mid가 peak면 (인접 원소 비교) 바로 mid 리턴

(2) 만약 mid가 왼쪽 원소보다 크면 증가하는 중이므로 오른쪽 영역에서 peak 탐색: left = mid + 1

(3) 만약 mid가 왼쪽 원소보다 작으면 감소하는 중이므로 왼쪽 영역에서 peak 탐색: right = mid - 1

 

재귀 / 반복으로 구현 가능

 

1) 반복으로 구현한 코드

class Solution(object):
    def findPeakElement(self, nums):
        n = len(nums)
        low, high = 0, n-1
        while low <= high:
            mid = (low + high) // 2
            if (mid == 0 or nums[mid-1] < nums[mid]) and (mid == (n-1) or nums[mid] > nums[mid+1]):
                return mid
            if (mid == 0 or nums[mid-1] < nums[mid]):
                low = mid + 1
            else:
                high = mid - 1
        return -1

Time: O(logn) / Space: O(1)

Runtime: 27 ms (beats 78.83%) / Memory Usage: 13.6 MB (beats 73.91%)

 

2) mid를 바로 반환하지 않고 low < high인 동안 반복을 돌린 다음에 low를 반환하는 코드

 

(1) mid가 오른쪽 원소보다 큰 경우 왼쪽~mid에 peak가 있는 것이고

(2) mid가 오른쪽 원소보다 작은 경우 mid+1~오른쪽에 peak가 있는 것임

범위가 엄청 헷갈리는데 그림 보고 생각해보면 좀 낫다.

 class Solution(object):
    def findPeakElement(self, nums):
        i, j = 0, len(nums)-1
        while i < j:
            mid = (i+j)//2
            if nums[mid] > nums[mid+1]:
                j = mid
            else:
                i = mid+1
        return i

 

3. max 원소의 인덱스 반환하기

배열에서 가장 큰 원소(max)는 peak일 수밖에 없다.

def findPeakElement(self, nums):
        return nums.index(max(nums))

Time: O(n) / Space: O(1)

Runtime: 32 ms (beats 39.82%) / Memory Usage: 13.5 MB (beats 93.02%)