LeetCode 코딩테스트 Minimum in Rotated Sorted Array – Array (7)

by

LeetCode는 소프트웨어 엔지니어링 및 코딩 인터뷰 준비를 위한 플랫폼이다. 다양한 프로그래밍 언어로 구현된 코딩 문제가 공하며 알고리즘 능력을 향상시키는데 도움을 준다.

LeetCode에 수 많은 문제 중에 시간을 절약하기 위해 New Year Gift – Curated List of Top 75 LeetCode Questions to Save Your Time 에서 각 카테고리/유형 별로 추천하는 75개 문제를 풀어본다.

이번 글에서는 Array문제인 Minimum in Rotated Sorted Array 문제를 python으로 풀어보았다.

leetcode-Minimum-in-Rotated-Sorted-Array

Leetcode 문제설명

이 문제는 크기 n의 정렬된 배열이 1부터 n번 회전되었을 때, 회전된 배열에서 최소값을 찾는 문제이다. 회전은 배열의 원소들이 한 칸씩 이동하면서 발생하며, 이진 탐색을 사용하여 O(log n)의 시간 복잡도로 문제를 해결해야 한다.

해당 문제는 https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/ 에서 확인 할 수 있습니다.

첫번째 예시의 배열 [3,4,5,1,2]는 [1,2,3,4,5]가 회전된 결과이며, 회전 횟수는 3번입니다. 따라서 최소값은 1입니다.

솔루션

다음 코드는 기본적으로 모든 경우를 탐색하여 최소값을 찾는 방법이기 때문에 시간 복잡도가 O(n^2)이다. 문제의 제약사항에서 O(log n)의 효율을 요구하고 있기 때문에 이 코드는 요구사항을 만족하지 않는다.

class Solution:
    def findMin(self, nums: List[int]) -> int:
        # 배열의 길이를 얻어옴
        n = len(nums)

        # 모든 원소 쌍을 비교하여 최소값을 찾음
        for i in range(n):
            for j in range(i + 1, n):
                # 현재 원소보다 다음 원소가 작으면 최소값이므로 해당 값을 반환
                if nums[j] < nums[i]:
                    return nums[j]

        # 만약 반복문을 빠져나오지 못했다면, 배열이 회전되지 않은 상태이므로 첫 번째 원소가 최솟값임
        return nums[0]

다음 코드는 이진 탐색을 사용하여 O(log n)의 시간 복잡도로 최소값을 찾다. 이 알고리즘은 배열이 회전되었다는 특성을 활용하여 탐색 범위를 조절하므로 효율적으로 동작한다.

class Solution:
    def findMin(self, nums: List[int]) -> int:
        # 초기 검색 범위 설정
        left, right = 0, len(nums) - 1

        # 이진 탐색 수행
        while left < right:
            # 중간 인덱스 계산
            mid = left + (right - left) // 2

            # 중간값이 오른쪽 끝 값보다 작으면 최소값은 왼쪽에 있음
            if nums[mid] < nums[right]:
                right = mid
            # 중간값이 오른쪽 끝 값보다 크면 최소값은 오른쪽에 있음
            else:
                left = mid + 1

        # left와 right가 수렴하면 최소값을 찾음
        return nums[left]

Leave a Comment