> [!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와 동일하지만 조금 메모리를 덜 쓴다.