[leetcode] 추천 75문제 중 1번. twoSum

 

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

불러오는 중입니다...

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

 

Example:

Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

 

배열이 주어지고 그 배열에서 두개의 정수의 합이 target에 맞을때 두 정수의 인덱스를 배열로 리턴하면 되는 문제이다.

 

처음에는 브루트 포스로 for문 2개로 모든 경우를 탐색했다.

그랬더니 108ms가 걸렸다.

 

var twoSum = function(nums, target) {
    for(let i=0; i<nums.length - 1; i++){
        for(let j=i+1; j<nums.length; j++){
            if(nums[i] + nums[j] === target) return Array(i,j);
        }
    }
};

이 방법 보다 더 좋은 방법이 있을까 고민하던 찰나,

 

예전에 알고리즘 스터디할때 잠깐 스치듯 배웠던 투포인터 알고리즘이 생각났다.

 

배열의 양끝에 포인터를 설정하고 두 정수의 합을 구해본다음에 두 합이 target보다 크면 좀 더 작은 수 두개를 더해야 한다는 의미이므로, 오른쪽 포인터를 왼쪽으로 옮기고 (정렬 되어 있기 떄문에 가능한 논리)

 

반대로, 두 정수의 합이 target보다 작으면 더 큰 두개의 정수를 더해야 한다는 의미이므로 왼쪽 포인터를 오른쪽으로 한칸 옮겨준다.

 

두 포인터는 겹치면 안된다고 문제에 명시 되어 있기 때문에 while문의 break 조건으로 걸어준다.(i != j)

 

var twoSum = function(nums, target) {
		let newNums = nums.map( (num, index) => {
			return Array(num, index);
		});
    newNums = newNums.sort((a, b) => a[0]-b[0]);
    let i=0,j=newNums.length-1;
		
    while(i != j) {
        let sum = newNums[i][0] + newNums[j][0];
        if(sum > target) {
            j--;
        }else if(sum < target) {
            i++;
        }else {
						console.log(Array(newNums[i][1], newNums[j][1]));
            return Array(newNums[i][1], newNums[j][1]);
        }
    }
}

하지만 답을 제출할때는 두개의 정수를 리턴해야하는게아니라 두 정수의 인덱스를 리턴해야 한다.

하지만, 내가 설명한 방법대로 구현하면 정렬을 하는 순간 원래 배열의 인덱스가 정렬된 배열의 인덱스와 맞지 않기 때문에 기존 정수로만 되어 있던 배열을 2차원 배열로 변경하고 각 인덱스의 배열의 두번쨰 인자로 원래 배열의 정수의 인덱스를 넣어주었다. 이렇게 하면 정렬이 되더라도 원래 정수의 인덱스가 유지되기 때문이다.

 

이것이 위의 코드보다 더 효율적이라고 생각했던 이유는 위의 경우 O(N2)의 빅오를 가진다.(for문 2개)

하지만 이코드는 비록 반복문을 여러번 돌긴 하지만 각 반복문이 O(N)이기 때문에 O(N2)보다 효율적일것이라고 생각했다.

 

실제 실행결과

76 ms

37.3 MB

로 기존

108 ms

34.7 MB

보다 속도는 줄었고 메모리 사용량은 늘었다.(정수 배열을 2차원 배열로 바꿨기 때문에 늘어남)

 

나중엔 시간과 메모리를 좀 더 줄여보도록 하자.