99클럽 코테 스터디 21일차 TIL(6월 10일) + 알고리즘 이분탐색

[문제 링크]

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

 

[문제 사고]

주어진 배열을 이분 탐색하여 주어진 목표값에 해당하는 배열의 index 값을 반환한다.

 

[문제 해결]

Solution - 1
1. 이분 탐색을 위한 first 값과 last 값을 선언 후 각 의미에 맞는 값을 할당해준다.
2. target 값이 nums 배열에 포함되어있지 않다면 nums 배열에 push 해주고 오름차순으로 배열을 정렬해준다.
3. 이분 탐색을 통해 target 값을 찾은 후 target 값의 index 값을 반환한다.

 

Solution - 2
1. target 값이 nums 배열에 포함되어있지 않다면 nums 배열에 push 해주고 오름차순으로 배열을 정렬해준다.
2. nums 배열 안에서 target 값의 인덱스 값을 indexOf method를 사용하여 반환한다.

 

[작성 코드]

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    //sol-1
    let first = 0;
    let last = nums.length - 1;
    if(!nums.includes(target)) nums.push(target)
    nums.sort((a,b) => a - b);
    while(first <= last){
        let mid = Math.floor((first+last) / 2);
        if(nums[mid] === target){
            return mid
        }else if(nums[mid] > target){
            last = mid - 1;
        }else if(nums[mid] < target){
            first = mid + 1;
        }
        return nums.indexOf(target)
    }
    //sol-2
    if(!nums.includes(target)) nums.push(target);
    nums.sort((a,b) => a - b);
    return nums.indexOf(target)
};

 

[문제 회고]

이분 탐색을 구현하는 가장 기초적인 문제였다. 이분 탐색으로 구현하여 답을 도출해내는 데에는 무리가 없었지만 문제 자체가 너무 기본적인 문제라서 이분 탐색을 사용할 필요도 없이 더 효율적인 방법이 있어서 2번 풀이로도 풀어보았다. 이분 탐색 알고리즘에 대한 이해도가 조금 쌓인 것 같다.