[C/LeetCode] Search in Rotated Sorted Array II

Daily LeetCoding Challenge March, Day 28

 

문제

정렬이 되어있는 배열을 (중복 가능) k 번 rotation 돌게 된 상태로 입력 받는다. 이때 몇번 회전되었는지는 모름

이 회전된 배열 안에 target number가 있는지 없는지 판별하는 것이다.

 

문제는 쉬움 그냥 배열 안에 요소가 있는지 없는지 확인하는 것임

따라서 접근 가능한 알고리즘은 많은데, rotation 된 특성을 활용해서 짜는 것이 문제의 핵심이다.

 

아이디어: Binary Search

이진 탐색을 쓰는데, 일단 어디서 회전 되었는지 알아야 하기 때문에 배열을 한번 검사해서 회전된 곳을 찾는다.

그 후 배열의 첫번째 값과 target number를 비교하여 어떤 앞 부분, 뒷 부분 중에서 어떤 곳에서 이진 탐색을 진행할지 찾아서 하면 된다.

 

예외 처리: 회전이 되지 않은 경우, 배열의 크기가 1

회전이 되지 않은 경우, 그대로 이진 탐색을 진행하면 된다.

배열의 크기가 1인 경우 첫번째 값만 비교하고 같지 않은 경우 바로 false를 return 하여 나머지 코드를 실행하지 않도록 따로 체크한다.

 

완성

submission: 8ms / 6.1MB

 

bool BinarySearch(int* nums, int numsSize, int target){
    int start = 0;
    int end = numsSize - 1;
    int mid;
    
    if (nums[start] == target || nums[end] == target)
        return true;
        
    while (start <= end)
    {
        mid = (start + end) / 2;
        if (nums[mid] == target)
            return true;
        else if (nums[mid] > target)
            end = mid - 1;
        else
            start = mid + 1;
    }
    
    return false;
}

bool search(int* nums, int numsSize, int target){
    int mid;
    
    if (nums[0] == target)
        return true;
    
    // 첫번째 값과 같지 않는 크기가 1인 배열은 false
    else if (numsSize == 1)
        return false;
    
    // 회전 기준점을 찾음
    mid = 0;
    for(int i=0;i<numsSize - 1;i++) {
        if(nums[i] > nums[i+1]) {
            mid = i + 1;
            break;
        }
    }
    
    // mid가 0인 경우 회전이 되지 않은 경우이므로 바로 이진 탐색을 진행함
    if (mid == 0)
        return BinarySearch(nums, numsSize, target);
    
    // 첫번째 값이 더 큰 경우, 기준점을 기준으로 뒷편에서 이진탐색을 진행한다.
    if (nums[0] > target)
        return BinarySearch(nums + mid, numsSize - mid, target);
    
    else if (nums[mid] == target)
        return true;
    
    else
        return BinarySearch(nums, mid, target);

}

 

 

단점

기준점을 찾아야 하기 때문에 일단 배열을 한번 linear search를 무조건 해야한다. 이게 아쉽다.

linear search를 하지 않아도 되는 방법이 존재할 것 같은데 고민해야한다.

 

 

CF

swift로 짜면 사실 한줄로도 작성 가능하다.

 

func search(_ nums: [Int], _ target: Int) -> Bool {
    return nums.contains(target)      
}

 

근데 이제 효율은 보장 못하는