2 분 소요

Binary Search

문제

문제 링크

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

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.

Constraints:

  • 1 <= nums.length <= 1000
  • -231 <= nums[i] <= 231 - 1
  • nums[i] != nums[i + 1] for all valid i.

스스로 고민

접근법

  • 가장 큰 숫자의 인덱스를 반환해주면 된다.
  • 피크는 여러 개가 있을 수 있지만 그냥 한 개만 반환하면 된다.

의사코드

  • 오름차순으로 정렬을 해준다.
  • 가장 마지막 숫자의 인덱스를 찾아서 반환해준다.

구현 코드

class Solution:

    def findPeakElement(self, nums: List[int]) -> int:

        sorted_nums = sorted(nums)

        x = sorted_nums[-1]

        y = nums.index(x)

        return y

시간 복잡도와 공간 복잡도

  • 시간복잡도: 주어진 코드의 시간복잡도는 O(n log n) 다. 이유는 코드에서 sorted(nums)를 사용하여 배열을 정렬하기 때문이다. 정렬 알고리즘의 시간복잡도가 일반적으로 O(n log n)이기 때문에 코드 전체의 시간복잡도도 O(n log n) 다.

  • 공간복잡도: 주어진 코드의 공간복잡도는 O(n) 다. 이유는 sorted_nums라는 새로운 배열을 생성하여 입력 배열 nums를 복사하고 정렬한 후 사용하기 때문이다. 따라서 추가적인 메모리 공간이 입력 배열과 정렬된 배열 두 개를 모두 사용한다.

회고 과정

테스트는 통과했지만 이진 검색이 아니라서 이진 검색으로 다시 만들어봤다.

지금 코드에서 뭘 개선할 수 있지?

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1

        while left < right:
            mid = left + (right - left) // 2  # 중간 인덱스 계산

            if nums[mid] > nums[mid + 1]:
                # 현재 중간 요소가 다음 요소보다 크다면 왼쪽 반쪽을 살펴봅니다.
                right = mid
            else:
                # 현재 중간 요소가 다음 요소보다 작다면 오른쪽 반쪽을 살펴봅니다.
                left = mid + 1

        # left와 right가 만나는 지점이 피크의 위치입니다.
        return left

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        # if curr mid is less than one of surrounding, we know it is
        # not a peak

        # l = 0
        # r = len(nums) - 1
        # while l <= r:
        #     mid = l + (r - l) // 2
        #     if nums[mid] >= nums[mid + 1] and nums[mid] >= nums[mid - 1]:
        #         return mid
        #     elif nums[mid] >= nums[l]:
        #         l = mid + 1
        #     else:
        #         r = mid - 1
        # return -1

        return nums.index(max(nums))
  • 파이썬 함수만 잘 알고 있다면 정말 쉽게 풀 수 있는 예

댓글남기기

참고