LeetCode | 1. Two Sum (*Hash Map)

문제

(링크)

풀이

const twoSum = (nums, target) => {
  let answer;
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        answer = [i, j];
        break;
      }
    }
  }
  return answer;
};

Follow-up: Can you come up with an algorithm that is less than O(n^2) time complexity?
이중 for문을 써서 O(N^2)시간이 걸리는 가장 간단한 방법으로 풀었다. 통과는 했지만 효율적으로 구현하기 위해 해시 맵을 이용하라고 한다.
해시 맵을 이용하면 삽입, 검색에 걸리는 시간 복잡도가 O(1)이므로, 전체 시간 복잡도를 O(N)으로 줄일 수 있다. 하지만 별도의 메모리 공간을 할당하기 때문에 공간 복잡도는 이중 for문 풀이 O(1)에서 O(N)으로 선형적(linear)으로 증가하게 된다.

참고

(링크)

const twoSum = (nums, target) => {
  let map = {};
  for (let i = 0; i < nums.length; i++) {
    let value = nums[i];
    let complementPair = target - value;

    if (map[complementPair] !== undefined) {
      return [map[complementPair], i];
    } else map[value] = i;
  }
};

Object 대신 Map 사용하기 ✔

const twoSum = (nums, target) => {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    let value = nums[i];
    let complementPair = target - value;

    if (map.get(complementPair) !== undefined) {
      return [map.get(complementPair), i];
    } else map.set(value, i);
  }
};

자바스크립트에서는 Object를 해시 맵처럼 쓰지 말라는 글¹을 읽어서 이러한 용도로 쓰기 위해 제공되는 Map을 사용해보았다.
객체는 key를 문자형으로 변환하지만, Map은 key의 타입을 변환시키지 않고 그대로 유지한다고 한다. 즉 자료형의 제약이 없다. 또한 맵은 설계 단계부터 데이터 추가, 삭제에 있어서 최적화되어 있기 때문에 단순히 객체를 이용할 때보다 성능 상 이점이 있다.
또한 map[key]는 Map을 쓰는 올바른 방법이 아니다.² 일반 객체처럼 취급하게 되기 때문인데, 따라서 Map 전용 메서드인 get과 set 등을 사용해야 한다.