[LeetCode] 153. Find Minimum in Rotated Sorted Array

문제

leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Find Minimum in Rotated Sorted Array - LeetCode

 

코드

(22년 2월 15일 구현)

class Solution {
    func findMin(_ nums: [Int]) -> Int {
        var leftIndex = 0
        var rightIndex = nums.count - 1
    
        if nums[leftIndex] <= nums[rightIndex] {
            return nums[leftIndex]
        }
    
        while leftIndex < rightIndex {
            let centerIndex = (leftIndex + rightIndex) / 2
            if centerIndex == leftIndex {
                break
            }
        
            if nums[leftIndex] < nums[centerIndex] {
                leftIndex = centerIndex
            } else {
                rightIndex = centerIndex
            }
        }
        return nums[rightIndex]  
    }
}

사이트 접속 환경에 따라 다르겠지만, 100% 찍힌건 처음이라 찍어봤어요. 큰 의미는 없습니다.

 

설명

투포인트로 left, right index를 설정하고, center을 계산하여 정렬여부를 확인해요.

 

처음, 오름차순 정렬이 제대로 돼있는지 확인합니다.

 

이후에 정렬이 안돼있다면, left, right 포인트를 사용하여 이진 탐색을 합니다.

그림으로 이해해 볼까요?

배열은 제가 만든 예제입니다.

 

다른 여러 방법이 있습니다.

 

재귀함수로 구현해봤어요. (21년 3월 22일 구현)

class Solution {

    func findMin(_ nums: [Int]) -> Int {
        if nums[0] <= nums[nums.count-1] {
            return nums[0]
        }        
        return searchBinary(nums)
    }

    func searchBinary(_ nums: [Int]) -> Int {
        var leftIndex = 0
        var rightIndex = nums.count-1
        
        while leftIndex < rightIndex {
            var midIndex = (leftIndex + rightIndex)/2

            if nums[midIndex] > nums[midIndex+1] {
                return nums[midIndex+1]
            } else if nums[midIndex-1] > nums[midIndex] {
                return nums[midIndex]
            } else if nums[leftIndex] > nums[midIndex] {
                rightIndex = midIndex-1
            } else if nums[midIndex] > nums[rightIndex] {
                leftIndex = midIndex+1
            }
        }
        return nums[0]
    }
}

이진탐색를, 매번 배열을 넘겨주는 재귀함수 구현으로 생각해봤는데

메모리 낭비가 될 것 같아, while로 구현했어요. (사실 함수로 뺄 필욘 없는데, 이해하기 쉽게 끔 따로 뺐어요)

searchBinary 메소드만 그림으로 이해해 볼까요?

 

단순 포문을 통해서 확인 가능해요.

class Solution {

    func findMin(_ nums: [Int]) -> Int {
        var result = nums[0]

        for i in 0..<nums.count-1 {
            if nums[i] > nums[i+1] {
                return nums[i+1]
            }
        }
        return result
    }
}

 

배열이 정렬돼있는 상태로 로테이션 된 상태이기 때문에,

index 0 번부터 n번까지 탐색하며 작아지는 순간(nums[i] > nums[i+1])을 찾으면 됩니다.

작아지는 순간을 찾지못했다면 nums[0]이 최소값인거죠.

 

또 sort하여 확인도 가능하겠죠??

회고

정답을 맞지만 로직이 너무 단순해서, 문제의 의도가 아니라 생각합니다.

로직의 최적화가 문제의 의도라 생각합니다.

사실 처음부터 이진 탐색으로 구현해야겠다고 생각했지만, 구현하기 넘 귀찮아서 포문으로 풀었더니 풀리더라구요;;;

아무튼, 오랜만에 이진탐색도 공부할겸, 이진 탐색으로 구현해봤어요.

이진 탐색은 중간 값을 비교하여 나아가는 탐색 방법이에요.포문으로 구현할 경우 6번 비교가 수행되지만, 이진 탐색으로 3번의 비교로 끝났네요