[LeetCode] Search for a Range - 자바스크립트 풀이

문제 링크

두시간 가까이 걸림.. 

 

1. 접근 방법

 

(1) 중복을 허용한 오름차순 배열이 주어지고 + O(logN) 시간복잡도로 풀으라고 했으며 + 피벗을 기준으로 왼쪽과 오른쪽의 값을 비교해야 하는 문제이므로 이진탐색으로 푼다.

 

(2) getIndex 라는 함수를 만들어서, 배열, 타깃, isLeftArray를 파라미터로 받아 주어진 타깃 범위의 첫 인덱스 또는 범위의 마지막 인덱스를 리턴하도록 한다.

const getIndex = (nums, target, isLeftIndex) => {
    if (nums.length === 0) return -1;
    let left = 0;
    let right = nums.length - 1;
    let mid = 0;

    if (isLeftIndex) {
	// ...
    } else {
	// ...
    }

    return -1;
}

 

(3) 타깃 범위의 첫 인덱스를 찾으려면 mid 값과 타깃을 비교해서 left, right를 옮겨준다.

이전에 풀었던 이진탐색 문제와는 달리, 중복을 허용하는 배열이 주어지기 때문에 mid 값과 타깃 값이 동일해도 mid를 리턴해주면 안 된다.

    if (isLeftIndex) {
        while (left + 1 < right) {
            mid = left + Math.floor((right - left) / 2);
            
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        // ...
    } else {
        while (left + 1 < right) {
            mid = left + Math.floor((right - left) / 2);
             
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        // ...
    }

 

(4) while문을 탈출하고 나면, left, right가 각각 남아 있다. 왼쪽 인덱스를 찾는 경우 left를 먼저 검사하고, 오른쪽 인덱스를 찾는 경우 right를 먼저 검사한다.

    if (isLeftIndex) {
        while (left + 1 < right) {
            mid = left + Math.floor((right - left) / 2);
            
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (nums[left] === target) return left;
        if (nums[right] === target) return right;
    } else {
        while (left + 1 < right) {
            mid = left + Math.floor((right - left) / 2);
             
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid;
            }
        } 
        if (nums[right] === target) return right; // right 먼저 검사
        if (nums[left] === target) return left;
    }

 

2. 전체 풀이

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) { 
    const answer = [getIndex(nums, target, true), getIndex(nums, target, false)];
    return answer;
};

const getIndex = (nums, target, isLeftIndex) => {
    if (nums.length === 0) return -1;
    let left = 0;
    let right = nums.length - 1;
    let mid = 0;
    
    // isLeft
    if (isLeftIndex) {
        while (left + 1 < right) {
            mid = left + Math.floor((right - left) / 2);
            
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (nums[left] === target) return left;
        if (nums[right] === target) return right;
    } else {
        // isRight
        while (left + 1 < right) {
            mid = left + Math.floor((right - left) / 2);
             
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid;
            }
        } 
        if (nums[right] === target) return right; // right 먼저 검사
        if (nums[left] === target) return left;
    }

    return -1;
}

아무튼 풀어냈음