[LeetCode/js] 1. Two Sum

LeetCode로 도전 시작

지금까지는 주로 프로그래머스로 알고리즘 문제를 풀었었다.
이후에는 백준으로 시도해봤는데,
좀 더 단계 별로 차근차근 문제를 풀고 싶기도 했고, 기준치를 두고 내 위치를 가늠해 보고 싶기도 했기 때문이었다. 보통 백준 100문제, 12단계까지 풀면 어느 정도 잘 하는 단계로 본다는 말을 들었어서 기준치를 두고 계획을 세워 공부할 수 있을 것 같았다. 그런데... 아직 실력이 많이 부족하다보니 ㅎㅎ 개인적으로 답답함이 느껴졌다. 입출력코드부터 해서 해당 기능을 구현하고 문제를 푸는 것 자체에는 큰 어려움이 없는데, 공부와 거리가 다소 있는 것들로 문제를 틀리고 시간을 낭비하는 느낌? 아직 적응을 못했나 보다.

코딩테스트는 영어로 문제를 출제하는 경우가 있어 영어가 익숙해지는 것이 좋다는 이야기를 들었다. 또. LeetCode가 여러모로 깔끔하고 재미있게 문제를 풀 수 있는 듯해 앞으로는 LeetCode를 애용해 보려 한다!

🎠Description

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

🎡Solution

1. My code

const twoSum = function(nums, target) {debugger
  let result = [];
  for(i = 0; i < nums.length; i++) {
    for(j = 0; j < nums.length; j++) {
      if(i !== j) {
        if(nums[i]+nums[j] === target){
          if(result.length <2){
            result.push(i);
            result.push(j);}
        }
      }
    }
  }
  return result;
}

2. other solution

var twoSum = function(nums, target) {
    const store = {}
    for(let i = 0; i < nums.length; i++){
      let cur = nums[i]
      let diff = target - cur
      // Return answer if the current number was a diff from a previous number
      if(store[cur]!==undefined) return [store[cur], i]
      // Set diff to current index in store
      else store[diff] = i
    }
};

3. other solution

const twoSum = (nums, target) => {
    let map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return  [map.get(complement), i ];
        }
        map.set(nums[i], i);
    }
};
//https://egg-programmer.tistory.com/238

개인적으로 이해하기 쉽지 않았다...
왜 이런 답안이 나오는지 뜯어본 바로는 다음과 같다.

[2,7,11,15] 중 합해서 9가 나오는 두 수를 찾을 때,
1. 2는 7과 더해야 9가 된다. Map객체에 7이 있는지 확인한다.
2. 없으니 2와 2의 인덱스인 0을 Map에 저장한다.{2:0}
3. 7은 2와 더해야 9가 된다. Map객체에 2가 있는지 확인한다.
4. 있다. 그러면 각 수의 인덱스는 어떻게 반환할까?
5. 현재 검사하고 있는 요소의 인덱스는 for문의 i값이다. arr[1] = 7이었으므로 (?,1(=i)) 두번째 인덱스 값은 i이다.
6. 7과 합해 9가 되는 수의 인덱스는 어떻게 구할까? 이를 위해 Map객체에 인덱스를 함께 저장해 두었다. {2(배열안의 수):0(수의 인덱스)} 따라서 Map객체에서 해당 요소의 value로 접근하면 된다. 즉, map.get(complement(=저장된 수 2))=0이다.
7. 따라서 [map.get(complement),i] = [0,1]로 반환된다.

🎈Review

Map 객체

Map오브젝트는 키 - 값 쌍을 보유하고있는 키의 원래의 삽입 순서를 기억한다.

const map1 = new Map();

map1.set('a', 1);
map1.set('b', 2);
map1.set('c', 3);

console.log(map1.get('a'));
// expected output: 1

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map

[ ] 이 문제는 꼭 안보고 다시 Map객체를 사용하여 풀어보자!