[Algorithm] [초급] 두 숫자의 덧셈

오늘은 간단한 알고리즘 “두 숫자의 덧셈"에 대해 알아보도록 하겠습니다.

문제

문제는 심플합니다. 함수의 파라미터에 두 변수를 입력받는데 첫 번째 nums 파라미터는 array를 받고 두 번째 target 파라미터는 숫자를 받습니다. 알고리즘의 목표는 nums array에 존재하는 숫자 두 개를 더하여 target 숫자를 만들어낼 수 있는 값들의 인덱스를 리턴해주면 됩니다. 예를 들어 아래와 같이 변수가 지정되었을 때

const nums = [2, 7, 11, 15];
const target = 9;
// 정답
const answer = [0, 1];

정답은 2와 7을 더해 9가 될 수 있으므로 2의 인덱스인 0 그리고 7의 인덱스인 1을 array 형태로 리턴해주면 됩니다. 여기서의 조건은 같은 숫자를 두 번 사용할 수 없고 nums 변수에는 target 값으로 합산될 수 있는 조합이 딱 한 가지밖에 존재하지 않습니다.

풀이

알고리즘 문제에 많이 익숙하지 않으신 분들이라면 nums array에서 룹을 두 번 돌려 9를 만들 수 있는 조합을 찾으려고 하실 수도 있습니다. 하지만 이렇게 되면 O(n²)가 되기 때문에 array의 사이즈 증가할수록 속도가 현저히 느려지게 됩니다.

올바른 풀이는 look up time 이 짧은 Map을 사용하여 이미 지나간 숫자들의 값과 인덱스를 저장하고 다음 인덱스를 볼 때 해당 숫자가 target 값을 만들 수 있는 값이 Map에 존재하는지 찾는 식으로 진행하시면 런타임을 O(1)로 줄일 수 있습니다. Javascript를 사용한 풀이 예제는 아래와 같습니다.

const twoSum = function (nums, target) {
    const table = {}; //테이블 생성

    let result;

    for (let i = 0; i < nums.length; i++) {
        const curNum = nums[i];

        const targetNum = target - curNum;

        if (table[targetNum] || table[targetNum] === 0) {
            result = [i, table[targetNum]]; //값을 찾을경우 룹 break

            break;
        } else {
            table[curNum] = i;
        }
    }

    return result.sort((a, b) => a > b ? 1 : -1);
};

console.log(twoSum([2, 7, 11, 15], 9));

문제는 LeetCode에서 참조하였습니다.

LeetCode