Javascript/LeetCode

1. Two Sum

모리군 2021. 8. 30. 01:29

최근 직장동료들과 함께 LeetCode를 하루 한 문제씩 도전하고 있습니다.

어려운 문제도, 쉬운문제도 있는데 오랜만에 20대 때의 마음을 가지고 편하게 즐겁게 임하고 있습니다.

 

Two Sum 문제는 매우 쉽지만, 2가지 정도로 해결할 수 있을 것 같습니다.

문제를 먼저 살펴보겠습니다.

 

* 문제 살펴보기

 

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.

 

> 매우 심플합니다. 1개의 정수 배열과 타겟이 주어지고, 두 수의 합이 target이 되는 2개의 인덱스를 포함하는 배열을 반환하면 됩니다.

 

  • Example 1:
    • Input: nums = [2,7,11,15], target = 9
    • Output: [0,1]
    • Output: Because nums[0] + nums[1] == 9, we return [0, 1].
      > 배열의 0번째 값인 2와 1번째 값인 7의 합이 9이므로 출력은 [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.

 

Follow-up: Can you come up with an algorithm that is less than O(n^2) time complexity?

 

Solution 1. Brute Foce

첫번째 솔루션은 그냥 단순하게 for문을 2번 돌려서  두 수의 합이 target이 되는 경우를 찾는 방법입니다.

이 방법을 통해 깔끔하게 두 수를 구할 수 있습니다.

문제에서도 n^2 이내에 동작하면 된다고 했으니 정답으로서 큰 문제는 없습니다.

 

* Source Code

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

 

Solution 2. Memorization

두 번째 솔루션은 HashMap을 이용하여, 기존의 값을 기억해 놓는 방법입니다.

 

0. Initialize

nums = [2, 4, 5, 1, 9, 3], target = 5, hash = new Map()

 

 

1. Loop - Step 1 (index= 0)

nums[0] 의 값은 2이고, 어떤 수를 더했을 때 5(target)이 되는지 찾습니다(find).

find는 3이고, hash에 3이란 값이 존재하는지 확인 합니다.

 

아직 hash에는 값이 비어있으므로 3을 찾을 수 없어서, nums[0]의 값을 기억해 두기 위해 hash에 저장해 둡니다.

 

 

2. Loop - Step 2 (index= 1)

nums[1] 의 값은 4이고, 어떤 수를 더했을 때 5(target)이 되는지 찾습니다(find).

find는 1이고, hash에 1이란 값이 존재하는지 확인 합니다.

 

아직 hash에는 1을 찾을 수 없어서, nums[1]의 값을 기억해 두기 위해 hash에 저장해 둡니다.

 

 

3. Loop - Step 3 (index= 2)

nums[2] 의 값은 5이고, 어떤 수를 더했을 때 5(target)이 되는지 찾습니다(find).

find는 0이고, hash에 0이란 값이 존재하는지 확인 합니다.

 

hash에는 0이 없기 때문에, nums[2]의 값을 기억해 두기 위해 hash에 저장해 둡니다.

 

 

4. Loop - Step 4 (index= 3)

nums[3] 의 값은 1이고, 어떤 수를 더했을 때 4(target)이 되는지 찾습니다(find).

find는 4이고, hash에 4이란 값이 존재하는지 확인 합니다.

 

hash에서 4를 찾을 수 있으며, [hash.get(find), index] 를 리턴하면 끝!

 

 

* Source Code

var twoSum = function(nums, target) {
    
    const hash = new Map();
    
    for( let i = 0 ; i < nums.length; i++) {
        // 1. target을 만들 수 있는 수 찾기
        const find = target - nums[i];
        
        // 2. target을 만들 수 있는 수를 찾는다면, 리턴
        if(hash.get(find) !== undefined)  return [hash.get(find), i];
        
        // 3. target을 만들 수 있는 수를 못찾았다면, 자신을 맵에 등록.
        hash.set(nums[i], i);
    }
    
    return [];
}

 

매우 간단한 문제였지만, 기존의 값을 기억하는 기법을 통해 조금 더 효율적이고 세련되게(?) 코드를 구현해 보았습니다.

 

다음 문제는 Linked List를 활용하는 Add Two Numbers 입니다.

저작자표시