> [!date] published: 2025-04-03 ## 문제 [Two Sum - LeetCode](https://leetcode.com/problems/two-sum/description/) `nums`의 원소들 중에서 두개를 더해서 `target`을 만들 수 있는 원소의 인덱스를 담은 배열을 구하는 문제 ## 풀이 1 ### 아이디어 단순하게 `nums`를 순회하면서 현재 원소(`num`)과 합해서 `target`을 만들 수 있는 원소가 있는지 확인한다. ### 코드 ```typescript function twoSum1(nums: number[], target: number): number[] { for (let idx = 0; idx < nums.length - 1; idx++) { const complementIdx = nums.indexOf(target - nums[idx], idx + 1); if (complementIdx !== -1) { return [idx, complementIdx]; } } // 타입 에러를 제거하기 위해 추가한 코드. // 답이 무조건 존재한다는 조건이 있었으므로 이 코드에는 도달하지 않는다. return []; } ``` ### 시간 / 공간 복잡도 `nums`를 순회하면서 (O(n)) `Array.indexOf` 메소드로 짝이 되는 원소를 찾는 방식 (O(n)) O(n)이 중첩되어 있으므로 **시간복잡도**는 **O(n<sup>2</sup>)** 이 된다. 답을 제외하면 추가로 필요한 공간이 없으므로 **공간복잡도**는 **O(1)** ## 풀이 2 ### 아이디어 O(n)보다 작게 만들 수 있는 방법은 인덱스를 찾는 데 걸리는 시간을 줄이는 것이라 생각해서 검색 시간이 짧은 Map을 활용했다. Map인 이유는 index도 함께 저장해야 하기 때문… `nums`의 원소를 key로, 그 index를 value로 하는 Map을 미리 만들어두고 시작했다. ### 코드 ```typescript function twoSum2(nums: number[], target: number): number[] { const numMap = nums.reduce((map, num, idx) => { map.set(num, idx); return map; }, new Map()); for (let idx = 0; idx < nums.length; idx++) { const complementIdx = numMap.get(target - nums[idx]); if (complementIdx !== undefined && complementIdx !== idx) { return [idx, complementIdx]; } } return []; } ``` ### 시간 / 공간 복잡도 Map을 생성할 때 O(n) Map에서 짝이 되는 원소를 찾는 것은 O(1)이므로 **시간복잡도**는 **O(n)** 이다. Map을 생성할 때 n만큼의 공간이 추가로 필요하므로 **공간복잡도**는 **O(n)** 이 된다. ## 풀이 3 ### 아이디어 짝을 찾는 for loop에서 Map에서 찾은 원소가 현재 원소와 동일한 것인지를 확인하는 조건문이 마음에 들지 않아서 좀 더 좋은 방법이 있는지 찾아보다 발견한 방법. Map을 미리 생성하지 않고 짝을 찾는 for loop에서 Map을 생성한다. `[a, b]`가 답일 때 지금까지는 `a`를 기준으로 `b`를 찾았지만 지금은 `b`를 기준으로 `a`를 찾게 되는 것! 원소의 짝을 찾을 때 현재 원소를 Map에 추가하기 전이기 때문에 맘에 들지 않던 조건문도 안 써도 된다. ### 코드 ```typescript function twoSum3(nums: number[], target: number): number[] { const numMap = new Map(); for (let idx = 0; idx < nums.length; idx++) { const complementIdx = numMap.get(target - nums[idx]); if (complementIdx !== undefined) { return [idx, complementIdx]; } numMap.set(nums[idx], idx); } return []; } ``` ### 시간 / 공간 복잡도 시간, 공간 복잡도 모두 풀이 2와 동일하지만 조금 메모리를 덜 쓴다.