logo
devhak

Two Sum

/LeetCode

문제 해석

요약

더한 값이 target 정수가 되는 배열의 두 요소를 구하여라.
두 요소의 인덱스를 배열로 리턴.

전문

🇰🇷 번역

정수의 배열이 주어지면, 더하면 특정 target과 같게 되는 두 숫자의 인덱스를 리턴해라.

정확히 한 개의 답만 있다고 가정하며, 같은 인자를 두 번 사용할 수 없다.

nums = [2, 7, 11, 15], target = 9으로 주어진다면 nums[0] + nums[1] = 2 + 7 = 9이기 때문에 [0, 1]을 반환
🇺🇸 원문

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]

🤔 문제 해결 방법 구상

  1. 배열인 nums를 순회하며 짝을 찾는다.

    • 순회해야할 것 같아서, 일단 만만한 for문 사용
    • 각 인자인 nums[i]를 설정하고 짝 찾기

  2. 짝의 값은 target - nums[i]

    • 짝의 값은 나오지만, 배열에 존재해야함
    • 매소드 indexOf 사용하여, 배열에 존재하는지, 존재한다면 인덱스가 무엇인지 도출

  3. 정답이 하나이므로, 조건에 맞으면 인덱스로 리턴

    • 배열에 존재해야하므로, indexOf의 값이 -1이면 안됨
    • 같은 인자를 두 번 사용할 수 없으므로, 인덱스가 i면 안됨
    • 정답이 하나이므로, 조건문 통과한다면 바로 리턴

코드구현

const twoSum = function(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    let pair = target - nums[i];
    let pairIndex = nums.indexOf(pair);

    if (pairIndex !== -1 && pairIndex !== i) {
      return [i, nums.indexOf(pair)];
    }
  }
};

결과 분석

Runtime: 172 ms
Memory Usage: 34 MB

리트코드분석 결과 런타임... 하위...따흑🥺...
일단 for문으로 순회하는 것이기 때문에 비효율적일거라고 생각했지만 생각보다 더 비효율 적인가 보다. indexOf 메소드도 한 몫 하는 것 같다.

리트코드의 solution을 보면, 내가 푼 방법은 Brute Force인것 같다. (내 코드가 무차별 폭격이라니....) for문을 한 번만 사용하지만, indexOf매소드 때문에 사실상 이중for문이다. 그렇게 되면 시간복잡도가 O(n)^2....

🧐 개선

리트코드의 solution을 살펴보니 Hash Table을 활용하는 것을 제안하고 있다. key-value 형태로 저장하는 hash table은 충돌하지 않는 이상 보통 시간복잡도가 n(1)이기 때문이다.

내가 사용한 indexOf처럼, 값을 찾기 위해 매번 순회화는 과정을 줄여야한다.
이런 상황을 막기 위해선 각 값에 대해 인덱스를 저장하고 있는 것이 필요하다. 배열요소-인덱스 형태로 저장을 한다면, 나중에 target조건에 맞을때 바로 인덱스를 불러올 수 있다.

객체를 하나 선언하여 저장하고 값을 리턴하거나, Map을 이용하여 get, set, has 매소드를 이용하는 것이 좋을 것 같다. 여기선 Map을 이용하여 개선 코드를 작성해볼 것이다.

개선 코드

  1. 배열 nums를 순회하는 것은 같다.
  2. 매번 인덱스를 찾지 않고, Object나 Map을 사용하여 값-인덱스 형태로 저장.
  3. 저장한 값이 있으면 리턴.
const twoSum = function(nums, target) {
  let map = new Map();

  for (let i = 0; i < nums.length; i++) {
    let pair = target - nums[i];

    if (map.has(pair)) {
      return [map.get(pair), i];
    }

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

개선 결과

Runtime: 60 ms
Memory Usage: 37.5 MB

속도가 훨씬 많이 개선되었다!
시간복잡도는 O(n), 공간복잡도는 O(n)으로 예상된다.

마무리

문제 통과가 어렵지는 않았지만, 속도를 개선하면서 Hash Table과 Map에 대해 고민해 볼 수 있던 문제였다.
앞으로 순환하면서 짝을 찾아야 하는 문제에선 무조건 for문(...)돌리지 말고 키-값으로 저장하는 형태를 먼저 떠올려야 할 것이다.

Reference & Learn More

MDN Map

Tags
Comments