Search Insert Position

문제

Given a sorted array 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 may assume no duplicates in the array.

정렬된 배열에서(중복된 값은 없다 가정) 타겟이 들어가야할 자리의 인덱스를 리턴해야하는 문제

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

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

Example 4:

Input: [1,3,5,6], 0
Output: 0

풀이

나의 코드

const searchInsert = (nums, target) => {
    if ( nums.indexOf(target) !== -1 ) {
        return nums.indexOf(target);
    } else {
        if ( nums.length === 1 ) return nums[0] > target ? 0 : 1;
        if ( nums[0] > target ) return 0;
        for ( let i = 0; i < nums.length; i++ ) {
            if ( nums[i] < target && nums[i+1] > target) return i+1
        }
        return nums.length;
    }
};

문제자체가 간단하기 때문에 그냥 포문으로 돌아서 코드를 작성했는데
통과는 했지만 예외처리를 몇가지나 해야하는 부분에서 코드를 쓰면서도 맘에 안들었고, 좋은 방법이 있을 것이라 생각이 들었는데 Discuss 탭을 보니 이진 탐색(Binary Search)을 쓸 수 있는 문제였다.

이진 탐색 ( Binary Search ) 이란?

정렬된 배열에서 특정 값을 찾을 때 사용할 수 있는 알고리즘.

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식.

처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

시간 복잡도는 O(logN)으로 빠르다.

문제를 이진탐색으로 풀면?

const searchInsert = (nums, target) => {
    let low = 0;
    let high = nums.length-1;
    while ( low <= high ) {
        let mid = parseInt((low + high)/2);
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] > target) {
            high = mid-1;
        } else {
            low = mid+1;
        }
    }
    return low;
}

위와같이 풀리며 매우 간단

Jump Game

문제

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

0번 인덱스를 시작점으로, 각 인덱스의 값만큼 점프해서 마지막 인덱스까지 갈 수 있는지 판별하는 문제

풀이

먼저 접근한 방법은 길이가 nums와 같은 새로운 배열에 0을 할당한 뒤에,
nums와 같은 인덱스에서부터 인덱스의 값만큼 다음 인덱스에 1씩 더해주는 방법으로 생각했음.( 이해안돼도 상관X, 쓰레기같은 방법이였음.. )

const canJump = nums => {
    let arr = [];
    for ( let i = 0; i < nums.length; i++ ) {
        arr.push(0);
    }
    for ( let i = 0; i < nums.length-1; i++ ) {
        for ( let j = i+1; j <= i+nums[i]; j++ ) {
            arr[j]++;
        }
    }
    return arr.lastIndexOf(0) === 0 ? true :false;
};

하다가 말아서 정확히는 아니고 대충 위와같이 코드를 작성했고, 시간복잡도는 n^2이 나오는데 테스트케이스에 n^2으로는 통과할 수 없을 정도로 긴 케이스가 있어서, 고민하다가 검색해보니 Greedy Algorithm이라는 방법이 있어 코드를 보고 아래와 같이 작성하니 시간복잡도 n으로 통과.

const canJump = nums => {
    let lastPos = nums.length-1;
    for ( let i = nums.length-1; i >= 0; i-- ) {
        if ( i + nums[i] >= lastPos ) {
            lastPos = i;
        }
    }
    return lastPos === 0;
};

Greedy Algorithm이란 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.

매트로이드라는 구조를 가진 문제에서는 그리디 알고리즘으로 항상 최적해를 찾을 수 있다.

위의 코드를 설명해보면

nums의 마지막 인덱스 값을 lastPos에 할당해놓고, 그 값부터 시작해서 lastPos를 0까지 도달하게 하는 것. 반복문 전체를 도는것이 아닌, 최적의 판단으로 횟수를 최대한 줄여준다.