Python으로 푸는 LeetCode 33. Search in Rotated Sorted Array

 

LeetCode 33. Search in Rotated Sorted Array

문제에서는 오름차순으로 정렬된 배열이 어떤 pivot을 기준으로 회전하였을 때, 특정 원소(target)이 몇 번째 Index에 위치했는지 반환하는 코드를 짜려고 한다. 

원소가 배열에 포함되지 않았을 경우 -1을 반환하면 된다. 원소는 중복되지 않는다. 

단, 알고리즘을 수행했을 때, 런타임 복잡도(runtime complexity)는 O(log n) 내에 수렴해야 한다.

LeetCode에 문제 보러 가기

LeetCode에서 푼 문제 리스트 바로 가기

github에서 코드 보기

 

 

문제에서 제시한 조건

- 어떤 pivot을 기준으로 회전을 한지 알 수 없다.

- 원소가 배열에 포함되지 않았을 경우 -1을 반환한다. 

- 알고리즘의 시간복잡도는  O(log n) 내에 수렴해야 한다.

Related Topic

Array, Binary Search

문제 풀이

이 문제는 Array, Binary Search와 관련이 있다. 이진 검색 알고리즘의 시간 복잡도는 O(log n)이다. 단, 이진 검색 알고리즘은 정렬된 배열에 한하여 적용할 수 있다. 이진 검색 알고리즘은 배열이 이미 정렬 되어 있기 때문에 배열의 중간 index를 기준으로 target이 왼쪽 오른쪽 중에 어느 부분에 포함되어 있는지 알 수 있어, 이를 기준으로 검색 범위를 반씩 줄여나간다. 이 문제에서는 오름차순으로 정렬되어 있던 배열이 회전되어 있기 때문에 이진 검색 알고리즘을 적용하기 어렵다고 생각 할 수 있다. 그러나, 배열을 잘 들여다보면 배열의 중간 index를 기준으로 왼쪽, 오른쪽 중 반드시 한 쪽은 정렬되어 있다. 정렬되어 있는 부분에 target 이 들어 있는지 확인해보자. 그렇다면 정렬되어 있는지 여부는 어떻게 확인을 할까. 왼쪽 부분에서 정렬된 배열이라면 첫 index와 중간 index의 값 중 중간 index의 값이 커야 한다. 오른쪽의 경우 중간 index의 값이 마지막 index의 값보다 작아야 한다.

정렬된 부분에 target이 포함되어 있는지 확인하고 있다면 그 부분으로 배열의 범위를 줄이면 된다. 없다면 제대로 정렬되지 않은 부분으로 범위를 줄여나간다. 이 작업을 반복하다보면 O(log n) 복잡도를 가진 변형된 이진 검색 알고리즘을 구현할 수 있다.

 

리뷰

처음 문제를 풀었을 때, 리스트에서 해당 값이 존재하는지 여부를 찾아주는 list.index() 메소드가 O(1)의 시간 복잡도를 가진다는 것을 알고 있었고 그렇기 때문에 문제는 3-4줄이면 정답을 제출 할 수 있었다. 근데 그건 출제자의 의도가 아닐테니 이진 검색 알고리즘으로 다시 풀게 되었다. 재밌었던 문제였기에 두가지 풀이를 모두 공유해두도록 하겠다.

 

파이썬 코드 - 이진 검색 알고리즘

def search(nums, target):
    length = len(nums)
    if length < 1:
        return -1
    return bst(0, length - 1, nums, target)
 
 
def bst(s_index, e_index, nums, target):
    mid_index = (s_index + e_index) // 2
    mid_value = nums[mid_index]
 
    if s_index > e_index:
        return -1
 
    if target == mid_value:
        return mid_index
 
    start_value = nums[s_index]
    start_index = s_index
    end_index = e_index
 
    # this section([4,5,6]) in ascending order ex) 4,5,6,(7) 0 1 2  target : 5
    if start_value <= mid_value:
        if start_value <= target and target < mid_value:
            end_index = mid_index - 1
        else:
            start_index = mid_index + 1
    else:
    # This part([6,7,0]) is not sorted in ascending order. ex) 6,7,0,(1), 2, 3, 4, 5  target : 0
    # Check the opposite side.
        if mid_value < target and target <= nums[e_index]:
            start_index = mid_index + 1
        else:
            end_index = mid_index - 1
    return bst(start_index, end_index, nums, target)
 
 
 
print(search([4,5,6,7,0,1,2], 0)) # 4
print(search([4,5,6,7,0,1,2], 3)) # -1
print(search([], 5)) # -1
print(search([3,1], 0)) # -1
print(search([5,1,2,3,4],1))  # 1

파이썬 코드 - 파이썬 내장 함수만 이용

 
#nums.index() time complexity : O(1)
def search(nums, target):
    try:
        return nums.index(target)
    except:
        return -1
 

 

코틀린 코드 - 이진 검색 알고리즘

class Solution33 {
    fun search(nums: IntArray, target: Int): Int {
        if (nums.isEmpty()) return -1
        return bst(0, nums.lastIndex, nums, target)
    }
    fun bst(s_idx: Int, e_idx: Int, nums: IntArray, targetValue: Int): Int{
        val midIdx = (s_idx + e_idx) / 2
        val midValue = nums[midIdx]
 
        // 언젠가 아래 두 조건 중에 하나에는 걸리게 되어 있음
        if (s_idx > e_idx) return -1
        if (midValue == targetValue) return midIdx
 
        val sValue = nums[s_idx]
        var nextSIdx = s_idx
        var nextEIdx = e_idx
 
        // 가운데를 기준으로 왼쪽/오른쪽에서 정렬되어 있는 방향을 찾아서 살핀다.
        if (sValue <= midValue){
            // 왼쪽이 정렬되어 있는 경우
            // 범위 내에 포함되어 있는지 확인한다.
            if (sValue <= targetValue && targetValue < midValue){
                nextEIdx = midIdx - 1
            } else {
                nextSIdx = midIdx + 1
            }
        } else {
            // 오른쪽이 정렬되어 있는 경우
            if  (midValue < targetValue && targetValue <= nums[e_idx]){
                nextSIdx = midIdx + 1
            } else {
                nextEIdx = midIdx -1
            }
        }
 
        return bst(nextSIdx, nextEIdx, nums, targetValue)
    }
}
 
fun main(){
    val solution = Solution33()
     var nums = intArrayOf(4,5,6,7,0,1,2)
     nums = intArrayOf(1)
    println(solution.search(nums, 3)) // 4
    println(solution.search(nums, 1)) // 0
}

 

 

#LeetCode 33.

 

Search in Rotated Sorted Array #LeetCode 33 #leetcode 33 #leetcode #Search in Rotated Sorted Array #LeetCode Search in Rotated Sorted Array #Search in Rotated Sorted Array 문제 풀이