1. Two Sum

문제

https://leetcode.com/problems/two-sum/description/

nums의 원소들 중에서 두개를 더해서 target을 만들 수 있는 원소의 인덱스를 담은 배열을 구하는 문제

풀이 1

아이디어

단순하게 nums를 순회하면서 현재 원소(num)과 합해서 target을 만들 수 있는 원소가 있는지 확인한다.

코드

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²) 이 된다.

답을 제외하면 추가로 필요한 공간이 없으므로 공간복잡도는 O(1)

풀이 2

아이디어

O(n)보다 작게 만들 수 있는 방법은 인덱스를 찾는 데 걸리는 시간을 줄이는 것이라 생각해서 검색 시간이 짧은 Map을 활용했다. Map인 이유는 index도 함께 저장해야 하기 때문…

nums의 원소를 key로, 그 index를 value로 하는 Map을 미리 만들어두고 시작했다.

코드

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에 추가하기 전이기 때문에 맘에 들지 않던 조건문도 안 써도 된다.

코드

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