[Leet Code Top 100] #33. Search in Rotated Sorted Array

문제 정보

• Leet Code 문제 링크
• 난이도 : Medium

 

해결 방법

이전에 풀었던 #153. Find Minimum in Rotated Sorted Array 문제와 비슷한데 Minimum 이 아닌 target 값을 찾는 문제입니다. 처음에는 이전 문제처럼 minimum 을 먼저 찾은 뒤 구간을 왼족 구간 ( nums[0] ~ nums[minIdx - 1] ) 과 오른쪽 구간 ( nums[minIdx] ~ nums[nums.length - 1] ) 으로 나누어 Binary Search 를 하려고 했었지만 Min 값 대신 target 값을 구하는 것으로 컨셉을 잡았습니다.

핵심은 rotate 된 정렬된 left side, right side 로 나누어서 target 과 nums[mid] 를 비교하면서 nums[mid] 를 target 쪽으로 이동시키는 것이었습니다. Binary Search 가 익숙하지 않아서 index 나 등호를 포함할지 하지 않을지, mid 값을 어떻게 나눌지 등 약간 고생을 했습니다. 구현에 시간은 좀 걸렸지만 시간 복잡도도 상위권이고 Discuss 탭에 올라온 답안과 동일하게 풀었습니다.

 

소스 코드

// Leet Code
// #33. Search in Rotated Sorted Array
// Success
// Runtime: 68 ms, faster than 95.78% of JavaScript online submissions for Search in Rotated Sorted Array.
// Memory Usage: 39.9 MB, less than 54.94% of JavaScript online submissions for Search in Rotated Sorted Array.

function main(){
    // Input // Output
    nums = [4,5,6,7,0,1,2], target = 0; // 4
    
    console.log(search(nums, target));
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    let idx = 0;

    while(left < right){
        const mid = Math.floor((left + right) / 2);
        //console.log(`nums[${left}]:${nums[left]} /nums[${mid}]:${nums[mid]} / nums[${right}]:${nums[right]}`);
        
        // nums[0] <= target : target is in left side
        // nums[0] > target : target is in right side
        if(nums[0] <= target && nums[0] <= nums[mid] ||
           nums[0] >  target && nums[0] >  nums[mid] ){
            // same side
            if(nums[mid] < target){
                left = mid + 1; // mid goes right
            } else {
                right = mid; // mid goes left
            }
        } else {
            // other side
            if(nums[mid] < target){
                right = mid; // mid goes left
            } else {
                left = mid + 1; // mid goes right
            }
        }

    }
    idx = left;
    //console.log(`idx:${idx}`);

    if(nums[idx] !== target){
        return -1;
    } else {
        return idx;
    }
};

main();

 

참고 자료

• LeetCode Top 100 Problem Selection
• LeetCode - Javascript - Simple O(log N) Binary Search Solution