[LeetCode 해석 및 풀이] 153. Find Minimum in Rotated Sorted Array

LeetCode 문제 해석 및 풀이 방법

 

문제 153. Find Minimum in Rotated Sorted Array(돌아간 정렬된 배열에서 최소값 찾기)

바로가기

 

문제 설명

영문

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

 

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

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

 

한글

길이 n의 정렬된 배열이 1~n번만큼 돌아갔다고 가정하자. 예를 들어, 배열 nums=[0,1,2,4,5,6,7]는 다음과 같이 된다.

 

• [4,5,6,7,0,1,2] 만약 4번 돌아갔다면
• [0,1,2,4,5,6,7] 만약 7번 돌아갔다면

[a[0], a[1], a[2], ..., a[n-1]] 배열을 1번 돌리면 결과는 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]가 된다.

 

돌아간 정렬된 고유한 숫자들의 배열이 주어지면, 해당 배열에서 가장 작은 원소를 구하시오.

 

무조건 O(log n)의 시간복잡도를 가진 알고리즘으로 작성해야 합니다.

 

제한조건

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All the integers of nums are unique.
• nums is sorted and rotated between 1 and n times.

 

입출력 예

입력	출력
nums = [3,4,5,1,2]	1
nums = [4,5,6,7,0,1,2]	0
nums = [11,13,15,17]	11

 

 

해답 및 해설

파이썬 (Python)

첫 번째 풀이

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if nums[0] < nums[-1]: return nums[0]

        left = 0
        right = len(nums)-1

        while left <= right:
            mid = (left+right) // 2

            if nums[left] < nums[mid]:
                left = mid
            elif nums[mid] < nums[right]:
                right = mid
            else:
                break
        
        return nums[right]

 몇번 돌아갔는지는 사실 의미가 없다 생각했고, 숫자가 증가하다 갑자기 감소하는 부분을 찾으려고 노력하였다. 우선 위와 같이 이진탐색을 하면 왼쪽은 계속 숫자가 올라가고, 오른쪽은 계속 숫자가 감소한다. 마지막엔 가장 큰 수와 가장 작은 수가 남게 되는데, 여기서 오른쪽 숫자가 최소값이라 이를 반환하게 하였다.

한바퀴를 완전히 돈 케이스는 특수하여 위 알고리즘이 통하지 않으므로 맨 처음에 제외시켜주도록 만들었다.

 

두 번째 풀이

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

        while left < right:
            mid = (left+right) // 2

            if nums[right] < nums[mid]:
                left = mid+1
            else:
                right = mid
        
        return nums[left]

다른 사람들의 풀이를 참고하여 특수케이스가 없는 풀이를 만들어냈다. 우선 left 인덱스를 옮길 때, mid에서 +1 한 값으로 옮기도록 하여 왼쪽에 최소값이 오도록 하였다. 그 후 조건으로 중앙값을 오른쪽 값과 비교하게 하여 [2, 1]과 같은 특수한 케이스에 대응하도록 한 풀이이다.