Search Insert Position 와 Minimum Operations to Exceed Threshold Value I

Topics

Arr, BinarySearch

문제 1 : Search Insert Position

요약 : 오름차순으로 정렬된 배열과 정수를 주고, 목표값과 같거나 목표값이 삽입될 수 있는 최소한의 위치값을 구하는 문제

var searchInsert = function(nums, target) {
    for(let i = 0 ; i < nums.length; ++i){
      //목표값과 같거나 목표값이 삽입될 수 있는 최소의 수 일 경우 return
        if(nums[i] == target || nums[i] >= target) return i
    }

    return nums.length
};

해결방법

주어진 배열이 오름차순으로 주어져 있었기에 목표값까지 순회하거나 커지는 수를 만날 경우 순서를 return 하는 방식으로 해결

주어진 문제가 일찍 해결되어 다른 문제를 추가로 풀어봄

이진탐색풀이

하지만 이 문제에서의 추가조건은 시간복잡도가 O(log n)을 만족하는 것이다. 위와 같은 풀이는 최악의 경우 O(n)의 시간복잡도를 가지게 됨으로써 반쪽짜리 정답이다. 그에 따라 이진탐색 알고리즘을 적용하여 풀어보기로 한다. 이진탐색은 기본적으로 주어진 배열을 절반으로 나누어 시작과 끝에서 한번씩 조건을 검사하여, 원하는 결과를 찾는 방법이다.

var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;

  	//시작과 끝이 교차하지 않을때까지
    while (left <= right) {
      	//절반의 인덱스
        const mid = Math.floor((left + right) / 2);
        //값이 같은 경우 return
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return left;
};

문제 2 : Minimum Operations to Exceed Threshold Value I

요약 : 무작위로 주어진 배열에서 제일 작은 수 하나씩 제거해가며, 목표값을 찾을때 까지 count 하거나 하나씩 제거된 후의 남은 배열의 모든 값이 목표값보다 클 경우 return

var minOperations = function(nums, k) {
    let result = 0
    while(true){
      	//최소값
        const min = Math.min(...nums)
        
        //목표값과 같은가
        if(min == k) break
      	//남은 배열의 수가 목표값보다 큰가
        if(nums.filter((value) => value < k).length == 0) break

        result += 1
      	//배열에서 최소값 제거
        nums.splice(nums.indexOf(min), 1)
    }

    return result
};

느낀점

코드를 풀고 느낀점보다 코딩테스트 관련 영상을 하나 보았는데, 효율적으로 코딩테스트 실력을 기르는 방법이다. 그 방법은 다음과 같다.

1. 코딩테스트는 문제은행식으로서 문제를 많이 풀어보았을 경우 유리하다
2. 난이도에 맞춰 몇개 이상 풀고 그 이상의 난이도에 도전하는 것은 비효율적이다. 그 보다 취약한 알고리즘 혹은 유형의 같은 난이도를 연속해서 풀어본다. 그 후 그에 대한 해답법을 기르고 어느 정도 익혔을 경우 난이도를 올리는게 효율적이다.
3. 처음으로 문제를 풀 경우 30~1시간 이내로 제한시간을 두어야 한다. 그 이상의 시간이 지나면 다른 사람들의 풀이를 보고 풀이 해법에 대한 방향이 비슷할 경우, 같은 유형의 다른 문제를 풀어본다. 이 때의 제한시간은 30분으로 한다.
4. 3번 문제에서 문제에 대한 방향성이 아예 다를 경우, 다른 사람들의 풀이를 보고 해법에 대해서 이해하되, 틀린문제QUEUE를 만들어서 추후에 다시 시도해본다.

이와 같은 방법들을 토대로 조금씩 다시 쌓아올려보겠다.