[leetCode] 35. Search Insert Position (Easy) 풀이

❓ 문제

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

 

고유한 정수의 정렬된 배열과 대상 값이 주어지면 대상이 발견되면 인덱스를 반환합니다. 그렇지 않은 경우 순서대로 삽입된 경우 인덱스를 반환합니다.

 

You must write an algorithm with O(log n) runtime complexity.

 

런타임 복잡도가 'O(log n)'인 알고리즘을 작성해야 합니다.

Example 1

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3

Input: nums = [1,3,5,6], target = 7
Output: 4

❗ 내 답변

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let idx = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] < target)
            idx = i + 1;
    }
    return idx;
};

처음엔 target보다 큰 경우, 작은 경우, 같은 경우 등을 모두 if 조건에 넣어 복잡하게 생각했었다.
하지만 곧 생각을 비우고 쉽게 다가가자 금방 풀 수 있었다.

 

nums를 차근차근 반복돌면서 target과 큰지를 비교하고 idx에 i + 1 값을 넣는다.
nums보다 target이 큰 경우가 단 하나도 없으면 별다른 조건 없이 idx의 초기 값인 0을 반환하게했다.
num 과 target이 같은 경우도 따로 고민할 필요 없었다. 어차피 크다, 작다로 판별하여 idx를 채우면
같은 수의 위치 index 와 동일한 결과 값이 나오게 되기 때문이다.

❗ Runtime이 가장 빨랐던 답변과 비교

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

const binarySearch = (nums, target, left, right) => {
    if(left <= right){
        let middle = Math.floor((left + right) / 2);
        if(nums[middle] === target)
            return middle;

        if(target < nums[middle])
            return binarySearch(nums, target, left, middle - 1);
        else
            return binarySearch(nums, target, middle + 1, right);
    }

    return left;
};

따로 binarySearch라는 function을 선언해줬다.
binarySearch에서 중간 값을 구하여 target과 비교하는 방식이었다.
반복문이 아닌 재귀함수로 반복작업을 하고 있다.

❗ Memory 사용이 가장 적었던 답변과 비교

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let start = 0;
    let end = nums.length-1;

    while (start < end){
        let mid = Math.floor((start + end)/2);
        if (nums[mid] === target) return mid;
        nums[mid] > target ? end = mid : start = mid + 1;
    }
    if (start === end){
        return target <= nums[start] ? start : start + 1;
    }
};

이 역시 중간 값을 구하여 target과 비교하는 방식이었다.
따로 function을 선언해주지는 않고 while 반복문을 사용하였다.

💡 개선 방안

모든 배열을 반복 돌지 않고 중간 값 비교를 통해 속도를 줄이는 것도 좋은 방법인 것 같다.