[LeetCode] 33. Search in Rotated Sorted Array

문제

leetcode.com/problems/search-in-rotated-sorted-array/

Search in Rotated Sorted Array - LeetCode

 

잠깐만

단순 포문으로 풀수 있겠지만, 문제 하단에 이런 문장이 있네요.

Follow up: Can you achieve this in O(log n) time complexity?

 

코드

class Solution {

    func search(_ nums: [Int], _ target: Int) -> Int {             
        var left = 0
        var right = nums.count-1

        while left <= right {
            var mid = (left + right) / 2

            if nums[mid] == target {
                return mid
            } else if nums[left] <= nums[mid] {
                if nums[left] <= target, target < nums[mid] {
                    right = mid - 1    
                } else {
                    left = mid + 1
                }
            } else if nums[mid] <= nums[right] {
                if nums[mid] < target, target <= nums[right] {
                    left = mid + 1    
                } else {
                    right = mid - 1    
                }
            }
        }
        return -1
    }
}

 

설명

이진탐색을 활용해야 하는데, 로테이션 된 배열이라, 여러 조건들이 추가되어야 합니다.

단순 이진 탐색으로만 풀려다보니, 머리가 안돌아가고 풀리지도 않더라구요.

아이패드로 끄적이다 보니, 규칙이 좀 보였습니다.

중간을 쪼개보면, 왼쪽이던, 오른쪽이던 어느 한 쪽은 오름차순으로 정렬돼있어요.

그래서, 아래 코드와 같이 mid(Index)를 기준으로 왼쪽 배열이 오름차순일 경우와 오른쪽 배열이 오름차순일 경우를 쪼갰어요.

    ...

} else if nums[left] <= nums[mid] {

    ...

} else if nums[mid] <= nums[right] {

    ...

}

 

그리고, 다음 코드와 같이 정렬된 배열 안에 target이 포함돼있는지를 확인했어요

 

왼쪽의 경우

if nums[left] <= target, target < nums[mid] {

    ...

} else {

    ...

}

 

오른쪽의 경우

if nums[mid] < target, target <= nums[right] {

    ...

} else {

    ...

}

 

이렇게 여러 케이스들을 상세화하니, 쉽더라구요.

다음 그림을 로직으로 구현했습니다.

 

 

회고

오랜만에 알고리즘 공부를 시작해서 그런지,

수도코드나 머리로는 이해되는데, 로직을 구현하지 못하겠더라구요.

좀 많이 분발해야겠네요;;;;