5/19 금 [LeetCode #1] 투썸 TIL

[LeetCode] 1. Two Sum

문제:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 104

109 <= nums[i] <= 109

109 <= target <= 109

Only one valid answer exists.

Follow-up:

Can you come up with an algorithm that is less than O( $n2$ ) time complexity?

나의 풀이:

// Nested for loop로 풀이
// Time complexity: O(N^2)
// Space complexity: O(1)?
function nestedSolution(nums, target) {
	for (let i = 0; i < nums.length; i++) {
		for (let j = i + 1; j < nums.length; j++) {
			if (nums[i] + nums[j] === target) {
				return [i, j];
			}
		}
	}

	return "No two numbers in 'nums' could be summed up to the target.";
}

// 정렬 후 양 끝 포인터를 옮기며 풀이 (two pointers, because we can assume there's only one possible pair to be the target.)
// Time comlexity: O(N) + O(NlogN) + O(N/2) => O(NlogN)
// Space complexity: O(N)?
function sortSolution(nums, target) {
	// 1. sort
	nums = nums
		.map((element, index) => ({ value: element, originalIndex: index })) // O(N)
		.sort((a, b) => a.value - b.value); // O(N) ~ O(NlogN) (Timesort)

	// 2. place two pointers at each end.
	let leftPointer = 0;
	let rightPointer = nums.length - 1;

	// 3. add two numbers and compare it with the target: 
	while (leftPointer < rightPointer) { // O(N/2)
		const leftValue = nums[leftPointer].value;
		const rightValue = nums[rightPointer].value;
		// if it exceeds the target, move the rightPointer to the left.
		if (leftValue + rightValue > target) {
			rightPointer--;
			continue;
		}
		// if it's less than the target, move the leftPointer to the right.
		if (leftValue + rightValue < target) {
			leftPointer++;
			continue;
		}
		// if it's the same with the target, return current pointers.
		if (leftValue + rightValue === target) {
			return [nums[leftPointer].originalIndex, nums[rightPointer].originalIndex];
		}
	}

	return "No two numbers in 'nums' could be summed up to the target.";
}

V8의 배열 정렬은 Tim sort(Merge sort과 Insertion sort를 섞은 방법)으로, 이미 정렬되어 있는 경우 O(N), 최악의 경우 O(NlogN) 시간 복잡도를 가진다.

실행 시간 측정:

module.exports.solution = sortSolution; 

const { performance } = require('perf_hooks');

function runTest(testFunction, testArray, target) {
	console.log('	Running test: ', testFunction.name);
	let start = performance.now();
	let result = testFunction(testArray, target);
	let end = performance.now();
	console.log('		Duration: ', end - start);
}

const testSizeList = [1000, 10000, 100000, 1000000];
for (const testSize of testSizeList) {
	let arr = [];
	for (let i = 0; i < testSize; i++) {
		arr.push(i);
	}

	console.log('Test size: ', testSize);
	runTest(nestedSolution, arr, 0);
	runTest(sortSolution, arr, 0);
}


// => 
Test size:  1000
        Running test:  nestedSolution
                Duration:  4.091300010681152
        Running test:  sortSolution
                Duration:  0.8199000358581543
Test size:  10000
        Running test:  nestedSolution
                Duration:  69.10749995708466
        Running test:  sortSolution
                Duration:  3.82779997587204
Test size:  100000
        Running test:  nestedSolution
                Duration:  5250.964500010014
        Running test:  sortSolution
                Duration:  19.394200026988983
Test size:  1000000
        Running test:  nestedSolution

// => 재측정: 
Test size:  1000
        Running test:  nestedSolution
                Duration:  4.866800010204315
        Running test:  sortSolution
                Duration:  0.5485000014305115
Test size:  10000
        Running test:  nestedSolution
                Duration:  64.30610001087189
        Running test:  sortSolution
                Duration:  5.4842000007629395
Test size:  100000
        Running test:  nestedSolution
                Duration:  5468.523400008678
        Running test:  sortSolution
                Duration:  54.932099997997284
Test size:  1000000
        Running test:  nestedSolution
                Duration:  644775.216899991
        Running test:  sortSolution
                Duration:  186.1094999909401

이중 for문으로 한 풀이와 정렬 후 풀이의 시간 복잡도를 구해보니 각각 O(N^2)과 O(NlogN)이 나왔는데, 테스트 결과 실제로 이중 for문의 경우 테스트 사이즈가 10배 증가할 때 걸리는 시간이 약 100배(=제곱 배) 증가하는 양상을 보였다.

자료 크기가 백만 개(1,000,000)일 때 이중 for문을 이용한 함수가 더 이상 실행되지 않았다. 이론상으로는 약 500초만 있으면 결과가 나와야 할텐데… 아! 50초가 아니라 500초구나. 실제로 10분쯤 기다리니 위와 같이 결과가 나왔다. 무려 10분 하고도 44초…

다른 풀이:

// target에서 현재 number를 뺀 값이 nums에 존재하는지 체크하는 방법. 매 number를 확인할 때마다 객체에 추가시킴으로써 nums 배열 자체를 탐색하는 시간을 없앤다. (Using "target - number" difference to see if that difference exists in "nums".)
// Time complexity: O(N)
// Space complexity: O(N)
function objectSolution(nums, target) {
	let obj = {};
	for (let i = 0; i < nums.length; i++) {
		const diff = target - nums[i];
		if (diff in obj) {
			return [obj[diff], i];
		}
		obj[nums[i]] = i;
	}

	return "No two numbers in 'nums' could be summed up to the target.";
}

나는 O(N^2) → O(N logN)까지 줄였는데 이 해법은 O(N)만으로 끝낸다. 잘하면 더 일찍 끝내버릴 수도 있고, 아주 깔끔하다. 어떻게 이런 생각이 가능하지? 나는 두 수를 ‘더한다’고만 생각했는데 ‘더해서 타겟이 되어야 한다’는 조건을 이리저리 뒤집어 가며 생각해본다면 비슷한 논리를 도출할 수도 있을 것 같다. 즉, ‘더해서 어떤 수’라는 건 ‘어떤 수에서 빼면?’이라고 명제를 달리해 볼 수 있다. 만약 ‘곱해서 어떤 수’라는 조건이 나온다면 ‘어떤 수에서 나누기’를 생각해 볼 수 있겠다.

하나 의문인 것은, map(~= object)을 이용할 때 왜 공간 복잡도가 O(N)인지이다.

※ 위 내용은 스스로 공부하며 적어둔 노트이며 불확실한 내용이 있을 수 있습니다. 학습용으로 적합하지 않음을 유념해주세요. ※

Uploaded by N2T

[LeetCode] 1. Two Sum

티스토리툴바