개요

LeetCode 추천 문제 75
오늘부터 위 링크의 문제들을 자바스크립트를 이용하여 풀어보겠습니다.

문제

twoSum

풀이

처음에는 그냥 생각나는대로 풀어보았다.
시간복잡도는 아마 최악의 경우 n제곱 나올 것이다. ( 아마 indexOf가 O(n) 시간복잡도)

const twoSum = function (nums, target) {
  for (let i = 0; i < nums.length; i++) {
    let sample = nums;
    let res = target - sample[i];
    sample[i] = true;
    if (sample.indexOf(res) != -1) {
      return [i, sample.indexOf(res)];
    }
  }
};

다른 풀이들을 보니 대부분의 사람들이 hash를 사용하여 O(n) 시간복잡도로 문제를 풀이하는것 같아서
ES6 에서 추가된 Map 타입을 가지고 풀이해보았다.

const twoSum = (nums, target) => {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const res = target - nums[i];
    
    // console.log(map)
    if (map.has(res)) {
      return [map.get(res), i];
    }
    
    map.set(nums[i], i);
  }
};

// ex
[2,7,11,15], 17

res에 target - nums[i] 값을 할당한다. nums 배열이 [2,7,11,15], tartget이 17라고 가정하면 첫 루프에서 res의 값은 7이다.

우선 if문은 건너뛰고

반복문을 수행면서 Map의 set 메서드를 사용하여 nums 요소의 value 값과 index 값을 Map의 key, value 값으로 설정했다.

Map(0) {}
Map(1) { 2 => 0 }
Map(2) { 2 => 0, 7 => 1 }
Map(3) { 2 => 0, 7 => 1, 11 => 2 }

if문에서는 map에 res값을 key 값으로 가지는 요소가 있을 경우 결과(인덱스 값) 리턴.

배운점

위 문제와 같이 배열에서 특정 값을 찾는 경우 이미 전에 계산했던 값이 현재 값 계산에 영향을 줄 수 있다. 그럴때는 앞에 저장한 값을 특정 저장소에 저장해두고 활용하면 좋을 것 같다.