⭐️ LeetCode 알고리즘 풀이 (with Python)

# Find Minimum in Rotated Sorted Array

[Quetion]

LeetCode 153. Find Minimum in Rotated Sorted Array

📌 접근법

[문제 이해]

• 회전된 배열에서 가장 작은 값 반환
• O(logn)의 시간복잡도

사실 가장 작은 값을 찾으려면 min()함수를 활용하면 되지만 min()함수의 시간복잡도는 O(n)이다.

그래도 min()로 return min(회전된 배열)을 제출 해보았는데 통과가 되었다(?)
왜 통과 되었는지 자세히는 모르겠지만, 테스트 케이스 리스트의 길이가 작아서 통과 된 것 같다고 생각했다.

또 떠오른 것은 sorted() 함수로 정렬 후, 첫번째 인덱스에 해당하는 값을 반환하는 것이다.

💻 구현

class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = sorted(nums) 
        return n[0]

Runtime: 44ms | Memory: 16.4MB
LeetCode 코드 중 Runtime 83%, Memory 97% 해당하는 결과

📝 Find Minimum in Rotated Sorted Array 회고

• 아무래도 함수를 활용한 점이 파이썬의 장점을 살리는 것이기도 하고, 편했다.

• 하지만 알고리즘 공부의 목적이기 때문에 함수를 활용한 간단한 구현 말고, 이진 검색의 방법으로 다시 접근하여 해결 해보았다.

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

        while l <= r:
            if nums[l] <= nums[r]:
                return nums[l]
            
            avg = (l + r) // 2

            if nums[l] > nums[avg]:
                r = avg
            else:
                l = avg + 1

Runtime: 44ms ---> 45ms
Memory: 16.4MB ---> 16.7MB

시간복잡도는 O(logn)으로 성능적으로는 이전 함수 활용 코드와 비슷한 성능을 가졌다.

회전하는 배열이기 때문에 완전 랜덤한 상태는 아니라 판단했고, 왼쪽과 오른쪽 포인터를 두어 맨 처음에 왼쪽이 작다면 회전하지 않았다고 판단하여 왼쪽 포인터가 가르키는 값을 리턴했다.

이후는 회전을 한 상태이기 때문에 포인터들 끼리의 중간 위치를 구하고, 왼쪽 값이 크면 오른쪽 포인터를 중간 위치로 옮기고 그 반대라면 왼쪽 포인터의 위치를 중간 값에서 1을 더한 값을 가르키도록 했다.

결국 핵심은 회전한 지점을 지나면 순서가 있기 때문에 이진 검색의 방법대로 가장 작은 값을 찾을 수 있었다.

크게 어려운 문제는 아니라고 생각했지만 생각하기까지는 시간이 꽤 걸려서 아직 더 열심히 문제를 풀어봐야겠다고 생각했다.