algo-wiki

Appearance

[Leetcode] 268. Missing Number ​

Problem ​

문제링크

nums 숫자 배열이 존재하고, 0~n까지의 숫자를 오직 한개씩 포함하고 있다. 배열에서 빠진 숫자를 구하여라.

만약 빠진 숫자가 없다면 마지막 값이 빠진것을 고려하자.

Solution ​

반복문, Binary Search

이 문제를 해결하는 방법은 두가지가 존재한다.

nums를 오름차순으로 정렬한다음 반복문을 이용해서 배열의 순서대로 인덱스(i)와 값(nums[i])을 비교하는 방법과 이진탐색을 이용해서 인덱스(i)와 값(nums[i])을 비교하는 방법

두 방법에서 답을 조건은 같지만 인덱스를 조건하는 방식은 다르다.

실행 방법빅오
반복문인덱스 순서대로O(n)
이진탐색찾을 범위를 줄임O(log n)

코드를 구현해보고 두 로직의 속도를 비교해보자.

반복문 코드 ​

  1. nums을 정렬해준다.
  2. 정렬한다면 nums의 값은 해당 인덱스와 값이 같아야한다. 만약 다르다면 이전 인덱스에서 어떤 값이 빠진것이다.
  3. 인덱스와 값을 비교하면서 값과 틀린 곳이 있다면 해당 인덱스를 리턴하고, 빠진 값이 없다면 마지막 요소가 빠진것으로 생각하고 마지막 값을 리턴한다.
ts
function forLoop(nums: number[]): number {
  nums.sort((a, b) => a - b)

  for (let i = 0; i < nums.length; i++) {
    if (i !== nums[i]) return i
  }

  return nums.length
}

이진탐색 ​

  1. 이진탐색 실행 조건의 nums 배열을 오름차순으로 정렬해준다. (값과 해당 인덱스가 같은 배열이 완성)
  2. left, right를 배열의 첫번째, 마지막 인덱스로 설정해준다. left와 right는 탐색 범위이다.
  3. 반복문을 이용해서 범위가 **하나의 요소로 좁혀질때까지의 조건(타겟)**을 추가해준다.
  4. 범위를 반으로 줄여가면서 탐색하는것이 이진 탐색의 원리이다. 이 원리를 이용해서 양쪽 인덱스를 중간 인덱스를 찾는다.
  5. 중간값(mid)과 중간값의 값(nums[mid])가 같은지 확인한다.
    • 만약 같다면 : 이전 인덱스에서 빠진 값이 없다는 것을 의미한다.
    • 틀리다면 : 이전에 어떤 값이 빠진 것을 의미
  6. 같을 경우 left의 범위를 변경해준다. (mid + 1), 틀린경우 이전 인덱스에서 타겟을 찾아야하기 때문에 right 범위를 변경해준다 (mid -1)
    • mid의 + 1을 해준 이유 : mid는 이미 확인한 값이기 때문에 다음 요소부터 확인. 그러면 left는 인덱스와 값이 틀린값을 최종적으로 가르킨다.
    • mid의 - 1을 해준 이유 : 위와 같인 이유(mid는 이미 확인한 값이기 때문에 이전 요소부터 확인)이면서 내가 찾는 타겟일 수 있다.
  7. left와 right는 하나의 값을 가르키게된다. 이것이 최초로 인덱스와 값이 틀린 요소입니다.
ts
function binarySearch(nums: number[]): number {
  nums.sort((a, b) => a - b)

  let [left, right] = [0, nums.length - 1]

  while (left < right) {
    const mid = Math.floor((left + right) / 2)

    if (mid === nums[mid]) left = mid + 1
    else right = mid - 1
  }

  return left === nums[left] ? left + 1 : left
}

비교 ​

배열의 사이즈를 100,000,000로 늘리고 마지막 인덱스 근방을 뺀 input을 만듭니다. 이 케이스는 순서대로 탐색했을 때 최악의 케이스를 만들었습니다. 그런다음 실행 시간을 출력하는 함수를 생성하여 실행했을때 입니다.

ts
function play () {
  const size = 100_000_000
  const input = Array.from(Array(size), (_,i) => i)
  input.splice(size-2,1)
  const timer = (fn: Function): void => {
    console.time(fn.name)
    console.log(`${fn.name} :: ${fn()}`)
    console.timeEnd(fn.name)
  }

  timer(binarySearch.bind(binarySearch, input))
  timer(forLoop.bind(forLoop, input))
}
bash
bound binarySearch :: 99999998
bound binarySearch: 1.427ms
bound forLoop :: 99999998
bound forLoop: 141.067ms

속도를 보면 이진탐색이 매우 빠른것을 확인 할 수 있습니다.

아래는 빅오계산법으로 속도 향상 폭을 보여주는 그래프입니다.

빅오