[CodeKata] twoSum 함수 구현하기

문제

twoSum 함수에 숫자배열과 '특정 수'를 인자로 넘기면, 더해서 '특정 수'가 나오는 index를 배열에 담아 return해주세요.

 

nums : 숫자 배열

target : 두 수를 더해서 나올 수 있는 합계

return : 두 수의 index를 가진 숫자 배열

 

예시) nums는 [4, 9, 11, 14]이며, target은 13이다. nums[0] + nums[1] = 4 + 9 = 13이다. 그러면 return 값으로 [0, 1]이 되야 한다.

 

풀이

첫 번째 코드

for(let i=0; i<nums.length; i++) {
	for(let j=0; j<nums.length; j++) {
    	if(nums[i] + nums[j] === target) {
        	const result = [i, j];
            return result;
        }
    }
}

 

중첩 for문을 사용했다. 중첩 반복문의 대표적인 예시로 구구단이 있다. 바깥 for문을 한 번 실행할 때 안쪽의 for문은 모든 반복을 실행한다는 점을 이용했다.

for(let i=1; i<10; i++) { // i=1이 실행되는 동안
	for(let j=1; j<10; j++) { // j를 1 ~ 10까지 모두 실행한다. 이후 i가 2로 증가하고 다시 j를 1~10 실행한다.
    	console.log(i + '*' + j + '=' + (i*j));
    }
}

 

그런데 코드가 돌아가는 결과를 일일이 적어보니 중복되는 부분이 상당히 많음을 알게 되었다. 파란색 부분은 이미 연산했던 부분을 중복해서 계산하고 있는 것이다. 이는 좋은 코드가 아니였음을 알게 되었고, 다른 코드에 대해서 생각하게 되었다.

 

 두 번째 코드

for(let i=0; i<nums.length; i++) {
	for(let j=i+1; j<nums.length; j++) {
    	if(nums[i] + nums[j] === target) {
        	const result = [i, j];
            return result;
        }
    }
}

j의 값을 i+1로 할당하여 중복된 계산을 하지 않도록 하였다.

 

흥미로웠던 코드

const twoSum = (nums, target) => {
	let result = [];
    for(let i in nums) {
    	let findNum = Math.abs(target - nums[i]);
        if(nums.indexOf(findNum) !== -1 && nums.indexOf(findNum) !== Number(i)) {
        	result.push(Number(i),  nums.indexOf(findNum));
            return result;
        }
    }
}

1. findNum에 (결과값 - 현재 인덱스 값)을 통해서 현재 인덱스 값에서 얼마를 더하면 되는지를 찾는 값을 저장한다.

 

2. nums에 findNum값이 없는 경우와 자기 자신을 더하는 값을 제외한 경우를 만족하면, result 배열에 현재 인덱스 값과 얼마를 더하면 되는지를 저장한 findNum의 위치를 저장한다.

 

단순히 중첩 for문을 사용하지 않으면 풀리지 않는 문제라고 생각했지만 해당 알고리즘 풀이를 보고 적잖이 놀랐다.