두 수의 합 (Two Sum) - LeetCode feat: javascript

정수 숫자와 정수 대상의 배열이 주어지면 두 숫자의 인덱스를 반환하여 대상에 합산합니다.
각 입력에는 솔루션이 하나만 있고 동일한 요소를 두 번 사용할 수 없다고 가정할 수 있습니다.
답변은 어떤 순서로든 반환할 수 있습니다.

 

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

Two Sum - LeetCode

 

실제 코딩테스트 시험을 보는거라면 안되겠지만 공부하는 중이라

처음에는 우선 문제해결에 집중하여 시간복잡도는 뒤로 두고 쉽게 풀어봤다.

 

우선 테스트 코드를 작성해주자.

 

요즘엔 테스트코드의 필요성과 공부 및 실제 개발환경에서 사용하고싶어 여러가지 이유로 테스트케이스도 작성했다.

 

const { twoSum } = require("./twoSum");

describe("twoSum", () => {
  it("입력에 대한 인덱스를 반환합니다", () => {
    const nums = [
      2, 7, 11, 15, 20, 25, 3, 4, 5, 6, 8, 9, 10, 12, 13, 14, 30, 31, 32, 33,
      34, 35, 36, 37, 38, 39, 40,
    ];
    const target = 9;
    const expected = [0, 1];
    const result = twoSum(nums, target);
    expect(result).toEqual(expected);
  });

  it("일치하는 인덱스가 없는 경우 빈 배열을 반환합니다", () => {
    const nums = [2, 7, 11, 15];
    const target = 5;
    const expected = [];
    const result = twoSum(nums, target);
    expect(result).toEqual(expected);
  });

  it("입력 배열이 중복된 숫자인 경우에도 유효한지 확인합니다.", () => {
    const nums = [3, 3];
    const target = 6;
    const expected = [0, 1];
    const result = twoSum(nums, target);
    expect(result).toEqual(expected);
  });
});

 

const twoSum = function (nums, target) {
  const result = [];
  nums.forEach((num1, index1) => {
    nums.forEach((num2, index2) => {
      if (index1 !== index2 && num1 + num2 === target && result.length < 2) {
        result.push(index1, index2);
      }
    });
  });

  return result;
};

우선 테스트코드도 잘 통과했고 문제해결 자체로는 상관없었으나 위 코드는 문제가 있다.

 

nums 의 길이가 최대 10^4 인게 문제다. 

시간 복잡도가 O(n^2)이므로 nums 배열이 커지면 성능이 크게 저하가 될거고 당연히 테스트도 실패할거다.

그렇다면 중첩반복문이 절대 들어가서는 안된다.

 

그럼 해쉬테이블을 이용하여 접근해보자.

 

const twoSum = function (nums, target) {
  let result = [];
  const keyValue = {};

  nums.forEach((num, index) => {
    const findNum = target - num;
    if (keyValue[findNum] !== undefined && result.length < 2) {
      result = [keyValue[findNum], index];
    } else {
      keyValue[num] = index;
    }
  });

  return result;
};

위 코드는 객체의 키값에 바로 접근하는 해쉬테이블을 이용했다.

반복문은 하나로 줄었으며 원하는 값도 한번에 찾을 수 있으므로 시간복잡도는 O(n) 이다.