[LeetCode] Search Insert Position

문제 링크

Can you solve this real interview question? Search Insert Position - 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. 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 Constraints: * 1 <= nums.length <= 104 * -104 <= nums[i] <= 104 * nums contains distinct values sorted in ascending order. * -104 <= target <= 104

https://leetcode.com/problems/search-insert-position

문제 요구 조건

문제는 간단했다. 숫자 배열과 타겟숫자가 주어진다.

숫자 배열은 겹치는 숫자가 없는 정렬된 배열이다.

타겟 숫자가 배열 내에 있으면 index를 반환한다.

타겟 숫자가 배열 내에 없으면 있어야될 위치의 index를 반혼한다.

나의 문제 풀이

문제를 받고 처음 들었던 생각은 그냥 경우의 수를 다 커버하면 된다고 생각했다. 그래서 testcase에 통과하고 또 다른 예외상황을 커버하는 식으로 풀어서, if 문이 많아 지게 되었다.

나의 문제 풀이

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
    let result;

    if (nums[0] > target) {
        return 0;
    }

    result = nums.indexOf(target);
    const last = nums.length - 1

    if (result === -1) {
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] < target) {
                if (i + 1 === nums.length && nums[i] < target) return nums.length
                if (nums[i + 1] > target) return i + 1
            }
        }
    }

    return result;
};

indexOf함수를 상요해서 타겟이 배열내에 있다면 바로 result에 대입

타겟이 배열내에 없을 때만 for문을 실행한다.

i+1이 마지막 인덱스를 넘어서는 경우를 커버한다.

정상적으로 타겟이 이전 인덱스와 다음 인덱스에 들어가야되는 경우를 커버한다.

나의 로직 같은경우는 특별한 것 없이 모든 경우의 수를 처리하는 방법이라서 생각보다 단순한 방법이라고 생각한다. 하지만 나의 머리로는 생각해보지 못한 풀이 방법이 있어서 가져왔다.

흥미로운 문제풀이

아래의 문제풀이는 이진검색과 같은 방법으로 문제를 해결하는 방식인 것 같다.

흥미로운 문제풀이 예시

JavaScript

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

    while (l <= r) {
        let mid = Math.floor((l + r) / 2)

        if (nums[mid] > target) {
            r = mid - 1
        } else if (nums[mid] < target) {
            l = mid + 1
        } else {
            return mid
        }
    }

    return l
};

제일 처음 첫 인덱스와 마지막 인덱스를 정해서 l 과 r에 할당한다. (left , right 인듯)

그담 while문에서 l 과 r의 중간 값을 인덱스로 사용한다.

중간인덱스 값보다 타겟이 작으면 r값을 mid값보다 1을 빼서 세팅한다.

반대의 경우에는 l값을 1을 더해서 세팅한다.

어떤 경우에 속하지 않은 경우에는 mid를 바로 리턴한다 → 타겟과 값이 일치

타겟이 이전값보다 크고 다음값보다 작은 경우에는 mid+1된 l값을 리턴한다.

느낀점

일단, 성능적으로는 아닌 경우를 바로 리턴하는 것이 제일 좋다고 생각한다. 하지만 수많은 if문으로 인해서 가독성이 조금 떨어질 것 같다고 생각한다.

두 번째의 흥미로운 문제풀이 방식은 이진 검색을 적용한 풀이 방식인데, 아무래도 이런 방식으로 문제를 해결해 본적이 없어서, 이런 풀이 방법이 떠오르지 않은 것같다. 확실히 배열이 아주 길어질 수록 이진 방법이 빛을 발할 것 같다고 생각한다. 그리고 이것도 익숙해 지는 방법이라고 생각한다. 내 머리속의 문제 해결방식의 도구가 되어가는 것이라 생각한다.