Two Sum, Hash Table | Leetcode [자바스크립트]

알고리즘과 자료구조를 공부하기 시작했다.

 

기존엔 알고리즘 문제를 풀 때 배운 언어를 적용하고 메소드들을 학습하는 데 치중했다면 앞으로는 알고리즘 기법이나 자료구조 등을 생각하면서 효율성도 신경을 써봐야겠다.

 

어쨌든 오늘은 Codewars가 아닌 Leetcode 문제를 풀어봤다. Codewars는 난이도가 세세하게 나눠져 있지만 뭔가 지겹고 문제들의 지시사항이 명확하지 않거나 영어가 이상해서 개인적으로 불편하다고 생각.. Leetcode는 runtime과 memory usage를 알려줘서 좋다. 그리고 화면이 깔끔하고 예쁘다. 다만 화면 전체를 어둡게 설정하진 못해서 눈이 좀 부시다.

 

Easy 1번 문제 Two Sum.

Two Sum - LeetCode

숫자로 이뤄진 배열(nums)과 목표 숫자(target)가 주어진다. 더한 값이 target인 숫자 두 개를 배열에서 찾아 각 숫자의 인덱스를 반환해야 한다. 조건에 부합하는 숫자 묶음이 딱 하나 있다고 전제.

1. for loop 안에 for loop

가장 쉽게 생각할 수 있는 방법으로 일단 써봤다.

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

요소들을 하나씩 순회하면서 합이 target이 되도록 만드는 요소가 있는지 추가로 배열을 훑는 방법이다. 단 nested for loop는 시작점을 i + 1로 설정했다. i가 거쳐온 값들은 또 확인할 필요가 없기 때문이다.

Time complexity는 O(n²). 상위 58% 정도라고 한다.

2. Hash Table

시간을 줄여보려 hash table을 이용해봤다. (사실 이런 게 hash map이 맞는지 아직 잘 모르겠지만)

1) 첫 시도

function twoSum(nums, target) {
  const container = {};
    
  for (let i = 0; i < nums.length; i++) {
    container[i] = nums[i];
  }
    
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
        
    if (Object.values(container).indexOf(complement) !== -1 && Object.values(container).indexOf(complement) !== i) {
      return [i, Object.values(container).indexOf(complement)];
    }
  }
}

Nested for loop을 없앴다. (그런줄 알았다.) Time complexity를 O(n)으로 줄이려 한 것이다. 

그런데 코드를 돌려보니 runtime과 메모리 모두 수치가 증가했다.

아래가 nested for loop을 이용했을 때, 위가 hash map을 이용한 첫 시도.

for loop 중첩을 없앤줄 알았지만 아닌 듯하다.

일단 Object.values()는 for..in과 마찬가지로 객체를 순회한다. (for..in은 프로토타입 체인을 따라 계속 돈다는 점에서 다르다.)

Object.values()

그리고 indexOf() 역시 내부적으로 loop을 활용하니 실행 시간이 늘어날 수밖에.

2) key, value 바꾸기

위에선 hash table을 만들 때 인덱스를 key, 요소 값을 value로 넣었다. 그래서 객체에서 요소를 찾을 때 value로 찾으려니 시간이 걸렸다고 생각하고 요소 값을 key, 인덱스를 value로 해서 다시 hash table을 생성했다. 그리고 hash table 탐색도 key를 기준으로 찾았다. 반환해야 하는 값이 인덱스니까 이 방법이 더 합리적인 것 같기도 하다.

function twoSum(nums, target) {
  const container = {};
    
  for (let i = 0; i < nums.length; i++) {
    container[nums[i]] = i;
  }
    
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
        
    if (complement in container && container[complement] !== i) {
      return [i, container[complement]];
    }
  }
}

결론적으로 시간을 절반 정도로 줄일 수 있었다. Time complexity는 O(n).

지금 글을 쓰다가 생각해보니 두 번째 for loop은 i < nums.length가 아니라 i < nums.length / 2로 설정해도 된다. 절반까지만 돌면 결과를 도출할 수 있기 때문이다. 어차피 그 뒤로 돌지도 않는다. 이미 return을 해버렸기 때문에.

3) Hash Table을 만들어가면서 complement 찾기

위 방법은 hash table을 모두 만든 다음에 for loop을 활용해 complement를 찾았다면 hash table을 만들어 가면서 동시에 complement를 찾는 방법도 있다. Hash table을 다 만들 필요없이 중간에 결과가 나오면 함수를 끝내버릴 수 있다.

function twoSum(nums, target) {
  const container = {};
    
  for (let i = 0; i < nums.length / 2; i++) {
    const complement = target - nums[i];
        
    if (complement in container) return [container[complement], i];
        
    container[nums[i]] = i;
  }
}

4) Map

그리고 마지막으로 객체가 아닌 Map을 써봤다.

function twoSum(nums, target) {
  const container = new Map;
    
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
        
    if (container.has(complement)) return [container.get(complement), i];

    container.set(nums[i], i);
  }
}

새로 공부한 내용이니 TIL에 따로 정리해봐야겠다.