오늘부터 알고리즘과 자료구조를 틈틈이 공부하기로 했다. 개발자의 인생을 걸으면서 실무공부 위주로 걸어왔는데, 최근 컴퓨터적 사고 능력과 문제 해결 능력을 키우기 위해 꾸준히 공부를 해야겠다고 다짐했다.

어떻게 공부할까 생각해보다가 LeetCode에서 자료구조를 공부하면서 문제를 계속 풀어보기로 하였다.

그리고 처음 푼 문제가 Two Sum 이다.

문제

이중 For문

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

배열들을 하나씩 순회하면서 i와 j인덱스에 해당하는 값이 target이 나오면 그것을 리턴하는 방식으로 하였다.

그리고 같은 배열일때는 그냥 넘어가도록 continue를 하였다.

이와 같은 방식으로 해도 테스트 통과가 이루어지지만 시간복잡도가 O(n2)로 그리 좋지많은 않다.

Hash Table을 이용

function twoSum(nums: number[], target: number): number[] {
    let result:number[] = [];
    let map = new Map();
    
    for(let i=0; i<nums.length;i+=1) {
        const diff = target - nums[i];
        if(map.has(diff) && map.get(diff) !== i) {
            return [map.get(diff),i];
        }
        map.set(nums[i],i);
    }
};

Map 생성자를 사용하여 해쉬테이블 자료구조를 사용한 케이스이다.

해쉬 테이블을 사용하면 key로 접근시 곧바로 value값을 얻을 수 있기때문에 시간복잡도는 O(1)이 나온다.

때문에 위의 코드에서는 반복문이 하나로 사용되고 결국 시간복잡도가 O(n)이 나와 훨씬 효율적이다.

배열을 순회하면서 해당 인덱스에 해당하는 값과 target을 빼준다.

그 빼준값에 해당하는 키값이 있고 그 밸류값이 현재 돌고있는 인덱스와 일치하지 않으면(같은 인덱스를 반환하면 안됨) 곧 바로 정답을 반환해준다.

그렇지 않으면 해당 배열의 value를 key값으로 지정해주고 인덱스를 그 key의 value로 set을 해준다.