[leetCode] 1. Two Sum (Easy) 풀이

❓ 문제

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.

 

정수 배열 nums 와 정수 대상이 주어지면 두 숫자의 인덱스를 반환하여 대상에 합산되도록 합니다.

각 입력에 정확히 하나의 솔루션이 있다고 가정하고 동일한 요소를 두 번 사용하지 않을 수 있습니다.

어떤 순서로든 답변을 반환할 수 있습니다.

Example 1

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: 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]

❗ 내 답변

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target)   
                return [i, j]
        }        
    }
};

Runtime: 193 ms
Memory Usage: 42.4 MB

 

배열 내에서 두 수의 합이 target과 일치하는 경우를 찾기 위해 이중 for문을 돌렸다.
이중 for 문을 돌려서 그런지 Runtime이 다소 늦었다.

❗ Runtime이 가장 빨랐던 답변과 비교

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let numberIndex = new Map();
    let result = [];
    for(let i = 0;  i < nums.length; i++) {
        let num = nums[i];
        let complement = target - num;

        if(numberIndex.has(complement)) {
            result[0] = numberIndex.get(complement);
            result[1] = i;
            return result;
        }

        numberIndex.set(num, i);
    }

    return result;
};

Runtime: 57 ms
Memory Usage: 43.5 MB

 

나와 달리 for 문을 한번만 사용했고, new Map() 을 사용했다.

Map

Map() 은 ES6 자바스크립트의 key-value 페어(pair) 로 이루어진 컬렉션이다.
key 를 사용해서 value 를 get, set 할 수 있음
key 들은 중복될 수 없음(하나의 key 에는 하나의 value 만)
key 로 사용할 수 있는 데이터형: functions, objects 등 어떠한 값이라도 가능

Object vs Map

Object 의 key 는 string 과 symbol(ES6) 만 가능하지만, map 은 어떤 값도 가능
Object 에서는 크기를 추적해서 알 수 있지만, map 은 손쉽게 얻을 수 있음(size())

 

이 문제에선, Object 나 Map 둘 중 어느 것을 사용해도 속도는 비슷한 것 같다.

 

위 코드를 요약하면,
Map()에 nums 의 숫자와 index 를 key, value 로 넣는다.
target과 nums 배열 내의 숫자를 서로 뺀 값이 Map() 에 존재하는지 찾고,
존재한다면 result 에 담아 리턴한다.

 

내가 반복을 돌면서 찾던 행위를 Map 의 get()으로 실행시켜준 셈이다.

❗ Memory 사용이 가장 적었던 답변과 비교

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let firstIndex, secondIndex;
    for(let i=0; i<nums.length; i++) {
        let index = nums.indexOf(target-nums[i]);
        if(index !== -1 && index != i) {
            firstIndex = i;
            secondIndex = index;
            break;
        }
    }
    return [firstIndex, secondIndex];
};

Runtime: 156 ms
Memory Usage: 42.7 MB

 

target과 nums 배열 내의 숫자를 서로 뺀 값에 대한 index를 찾고
index가 존재하면 배열에 담아 리턴하는 방법이다.

 

leetCode 통계에서 Memory 사용이 가장 적다고 나오긴 했으나 사실 크게 차이 없는 것 같다.

💡 개선 방안

for 문 사용을 최대한 줄이고 Map() 이나 Object 를 활용한다!