Leetcode 1. Two Sum

릿코드 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.

 

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]

 

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

문제설명

구현해야 하는 함수는 인자를 두개를 받습니다.

첫번째 인자는 integer 로 이루어진 배열, 두번째 인자는 int 입니다.

첫번째 인자로 들어오는 배열중 두가지 int 값을 더했을 때, 두번째 인자로 받은 int 값과 같아지는 방법이 있는지, 있다면 두가지 선택된 int의 index 값을 배열로 리턴해줘야 합니다.

Two Sum 문제의 경우 역시 주니어 개발자 포지션의 단골 문제로, 잘 숙지해두면 좋을 거 같습니다.

---

이 문제는 두 값을 더해서 리턴할 수 있는 값이 배열 안에 단 하나만 존재한다는 전제를 두고 있습니다.

예를 들면, nums = [3, 3, 2, 6, 4], target = 6 의 경우 3+3 도 6이고 2+4도 6이어서 [0, 1], [2, 4] 이렇게 두가지 정답이 존재하므로 이런 배열은 들어오지 않는다는 전제를 두고 있습니다.

그래서 인덱스를 찾는 대로 바로 리턴을 해주는 방법으로 가면 됩니다.

우선 brute-force 방식으로 접근해 보겠습니다.

/**
 * @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];
        }
    }
};

 

for 루프를 두번 돌면서 모든 경우의 수를 다 더해 인덱스 배열을 리턴해 줍니다.

이 경우 Time Complexity 가 O(n^2) 이 되어 퍼포먼스가 다소 좋지 않습니다.

brute-force 방식으로 접근 성능입니다.

 

실제로 통과는 했지만 더 좋은 방법으로 문제를 접근해 보도록 하겠습니다.

---

Map 사용해서 풀기

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const hashTable = new Map();

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

        if (hashTable.has(diff)) {
            return [i, hashTable.get(diff)];
        } else {
            hashTable.set(num, i);
        }
    }
};

 

이번에는 Map 으로 문제를 풀어보았습니다.

hashTable 이라는 맵 객체를 하나 만들어 줍니다.

for 루프를 한번만 돌며 도는 중 해당 배열의 int는 Key 값으로, 인덱스는 Value 값으로 set 을 해줍니다.

만약 해쉬테이블에 루프를 돌때, 해쉬테이블의 키 값이 target - num 일 경우에 해당루프의 인덱스 값과(i), 해쉬테이블 중 target - num 의 Value 값을 리턴하면 됩니다.

이 경우, Time Complexity 가 O(n)이 되어 전의 접근 방식보다 훨씬 성능 향상을 기대할 수 있습니다.

 

성능이 훨씬 더 좋아졌습니다.

---

저번에 풀어보았던 valid anagram 문제에서도 Map 객체를 이용했었는데요.

Map 객체에서 이용 가능한 메소드인 has 함수는 Set 과 Map 객체에서 사용이 가능합니다.

 

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

Set.prototype.has() - JavaScript | MDN

 

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

Map.prototype.set() - JavaScript | MDN

 

필요하신 분들은 문서를 확인해 보시면 좋을 듯 합니다.

이상 Two Sum 릿코드 문제를 풀어보았습니다.

---

※ 앞으로 모든 문제를 JavaScript 로 올릴 예정입니다.

 

다른 문제 풀이도 깃헙에서 확인 할 수 있습니다.