[LeetCode/JS] 1.Two Sum - 2가지 풀이 방법

문제 링크

• https://leetcode.com/problems/two-sum/submissions/

문제 설명

1. 숫자로 이뤄진 배열과 타겟 숫자가 주어진다.
2. 숫자를 합쳤을 때 주어진 타겟 숫자를 충족시키는 원소들의 인덱스를 반환해랏

주제

• Brute Force, Hash Table, Array

난이도

• Easy

1차 풀이 - Brute Force

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

const twoSum = function(nums, target) {

    result = []
    
    for(let i=0; i<nums.length; i++) {
       for (let j=i+1; j<nums.length; j++) {
           if(target === nums[i] + nums[j]) {
               result.push(i,j)
               return result

           }
       }
    }
  
}

풀이 방법

1. 중첩 루프를 이용하여 배열 내 값을 일일이 더해서 타겟 숫자를 충족시킬 경우 인덱스를 반환한다.

시간 복잡도

• O(n2)

2차 풀이 - Hash Table

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

const twoSum = function(nums, target) {
    const table = new Map();	// 값을 저장시킬 테이블 생성
    
    for(let i=0; i<nums.length; i++) {
        // 현재 값에서 타겟 값을 충족시키기 위한 숫자를 구한다.
        let curNum = target - nums[i]   

        // 만약 table에 충족시켜주는 값이 있다면 현재 인덱스와 해당 값의 인덱스를 반환한다.
        if(table.has(nums.indexOf(curNum))) {    
            return [i, nums.indexOf(curNum)]
        }     
        table.set(i, nums[i])
    }  
}

풀이 방법

1. 숫자 배열을 key와 value로 나누어 map 에 저장한다.
2. 현재 인덱스의 값과 타겟 숫자를 비교하여 타겟 숫자를 충족시킬 수 있는 값이 테이블에 있는지 확인한다.
3. 만약 있을 시 현재 인덱스와 테이블에 저장되어있는 key값을 반환.
4. 없을 시 테이블에 현재 인덱스를 저장하고 다음 인덱스로 넘어간다.

참고
arr.indexOf(값) - 값의 인덱스를 알려준다.
map.set(k,v) - 맵의 key와 value를 저장한다.
map.has(k) - key의 존재여부를 알려준다. (true/false)

시간 복잡도

• O(n)

문제를 풀고 알게된 개념 및 소감

Brute Force 방법을 생각했을 때는 풀이 방법이 매우 쉽다고 생각했다.
하지만 LeetCode의 Follow-up 도발로 좀 더 파고드니 Hash Table를 이용한 방법이 있다는 걸 배웠다.

문제에서 제공하는 test case 범위가 작아 시간 복잡도라는 개념이 크게 다가오진 않았다. 하지만 나중에 숫자가 커졌을 때는 체감할 수 있을 정도의 시간 차가 생기겠지? 그런 상황을 대비해 이렇게 자료 구조 공부를 하며 준비해놓고 있어야겠다!