LeetCode Two Sum 풀이: 이중 반복문과 해시 테이블로 시간 복잡도 비교하기

TL;DR#

• 알고리즘 공부를 시작하며 LeetCode의 첫 문제로 Two Sum을 풀어봤습니다.
• 이중 반복문으로 풀면 통과는 되지만 시간 복잡도가 O(n^2)입니다.
• 해시 테이블(Map)을 쓰면 반복문 하나로 O(n)에 해결할 수 있어 훨씬 효율적입니다.

알고리즘 공부를 시작하며#

오늘부터 알고리즘과 자료구조를 틈틈이 공부하기로 했습니다. 개발자로 일하면서 그동안 실무 공부 위주로 걸어왔는데, 최근 컴퓨터적 사고 능력과 문제 해결 능력을 키우려면 꾸준한 공부가 필요하겠다고 다짐했습니다.

어떻게 공부할지 고민하다가 LeetCode에서 자료구조를 익히며 문제를 계속 풀어보기로 했습니다. 그리고 처음 푼 문제가 Two Sum입니다.

bookmark

이중 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(n^2)라 그리 좋지 않습니다.

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의 차이(diff)를 구합니다.
• 그 diff에 해당하는 key가 이미 있고, 저장된 value가 현재 인덱스와 다르면(같은 인덱스를 반환하면 안 되므로) 곧바로 정답을 반환합니다.
• 그렇지 않으면 현재 값을 key로, 인덱스를 value로 Map에 저장합니다.

정리#

같은 문제라도 자료구조를 어떻게 선택하느냐에 따라 시간 복잡도가 O(n^2)에서 O(n)으로 달라집니다. 해시 테이블의 O(1) 조회를 활용하면 중첩 반복문을 한 번의 순회로 줄일 수 있다는 점을 첫 문제부터 확인할 수 있었습니다.