알고리즘 뒤풀이-leet34

회사에서 javascript 를 사용하게 되었고 관련된 책과 강의도 들었지만 더 자유자제로 사용하기 위해서는 개인 프로젝트도 해보고 알고리즘 문제도 풀어봐야 한다고 생각한다.

그래서 오늘 leetcode34번 문제 를 풀었다. 시간복잡도 O(log n)을 요구하여서 이분 탐색(binary search)를 이용하여 문제를 풀었고, 다른 사람들의 풀이 중 의문이 생겨서 이 의문을 해결하는 과정을 글로 남긴다.

javascript Array Object가 제공하는 메서드를 이용한 풀이이다. includes 를 이용해 값의 존재 여부를 판단하였고, indexOf 를 이용해서 굉장히 짦은 코드안에서 문제를 해결했다.

var searchRange = function(nums, target) {
 if(!nums.includes(target)) {
    return [-1,-1]
  }
  for(let i=nums.indexOf(target); i<=nums.length; i++) {
    if(nums.indexOf(target, i) === -1) {
      return [nums.indexOf(target), nums.indexOf(target, i - 1)]
    }
  }
};

처음에는 깔끔하고 읽기 좋은 코드라고 생각했는데, 두번 보니 includes 와 indexOf 를 쓰면 시간 복잡도 O(log n)을 달성할 수 있나? 의문이 들었다.

ECMAScript 를 살펴보자. 솔직히 이 문서까지 찾아보는건 오버하는것 같긴 한데, 하는김에 제대로 하보자.

Array.includes 메서드

이 메서드의 원형은
Array.prototype.includes ( searchElement [ , fromIndex ] ) 이다.
fromIndex 는 그 이름에서도 유추 가능하듯이 몇번째 index 부터 탐색을 할 것인지 설정하는 것이다.

아래 이미지는 includes 메서드가 호출되면 일어나는 일을 절차대로 적어놓은 부분을 캡쳐한 것이다. MDN 에서는 이 부분을 직접 코드로 구현해서 예시를 보여주고 있다. MDN 폴리폴

ToObject, LengthOfArrayLike 등은 너무 세부적인거라 내 의문을 푸는데 중요한 요소는 아니었다. 이 절차를 간단히 말하면 k < len 까지 k를 1씩 증가시키며 일치하는 값을 찾는다는 것이다. 즉, 선형 탐색(linear search) 가 된다.

Array.indexOf

이 메서드의 원형은 Array.prototype.indexOf ( searchElement [ , fromIndex ] ) 이다. 내부 로직은 기능은 includes 와 유사하지만, 디테일한 부분에서의 차이점과 반환 값이 다르다.

역시 선형 탐색이다.

두 메서드의 디테일한 차이점은 내부적으로 판단하는 로직이 다르다는 것이다.

# includes :
SameValueZero(x, y) 
# indexOf :
IsStrictlyEqual (x, y)

SameValueZero(x, y) 는 NaN 까지도 동일성 판단해주지만, IsStrictlyEqual(x, y) 는 NaN이 들어오면 모두 false 로 처리해버린다.

결론

결론은 위의 풀이는 시간복잡도 O(log n)을 지키지 못한 풀이이다. 하지만 나에게 이 자료를 공부하게끔 만들어준 의미있는 풀이었다.