자바스크립트 릿코드 #1 Two sum

들어가며

이 포스팅에서는 leetcode 추천 문제 top 75를 자바스크립트로 풀어보며 자바스크립트 공부와 알고리즘 공부를 동시에 합니다. 문제와 풀이를 적을 건데, 틀린 부분이나 더욱 개선될 부분이 있다면 댓글로 달아주시면 정말 감사하겠습니다.

문제

Two sum

문제 설명

문제 개요

이 문제의 입력은 nums(숫자의 배열)와 target(하나의 숫자)이 들어옵니다.
문제의 핵심은 nums 배열에 있는 숫자 중 2개를 사용하여, target에 해당하는 숫자를 만드는 것입니다.

이 문제의 출력은 nums 배열의 몇번째 인덱스를 합쳐야 하는지 순서대로 표기하는 것입니다.

예제

이를테면 nums에 [1, 2, 3, 4]가 들어오고 target에는 3이 들어온다면
올바른 출력 값은 [0, 1]이 될 것입니다.

풀이 과정

제 생각에는 일단 배열을 삽입정렬과 비슷한 방법으로 loop를 돌리면서 2숫자의 합으로 나올 수 있는 경우의 수들을 구해보다가 맞는 경우 즉시 리턴하면 될 것이라 생각했습니다.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  for (var i = 0; i < nums.length; i++) {
    for (var j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }

  return []; // no answer
};

대략 이러한 답을 내놓았고, 시간복잡도는 삽입정렬과 비슷하게 최악의 경우 n제곱, 최상의 경우에는 n만에 풀리게 됩니다.

또한 제가 푼 답변 말고 다른 추천수가 높은 자바스크립트 답변을 구경해보았습니다. 그 사람의 정답은 다음과 같았습니다.

const twoSum = (nums, target) => {
  const map = {};

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

    if (another in map) {
      return [map[another], i];
    }

    map[nums[i]] = i;
  }

  return null;
};

어떻게 처음부터 이런 생각을 하게 되었는지는 궁금하지만, hash를 이용하여 n의 복잡도로 문제를 깔끔하게 풀어버립니다.

설명하자면,

another라는 변수를 사용하여, target - nums[i] (현재 nums 배열의 값) 을 저장합니다.
이를테면 nums에 [2, 7, 11, 15]라는 값이 들어있고, target에 9라는 값이 저장되어 있다고 가정할 때, another의 값은 2가 됩니다.

그리고 일단, if문에 대한 설명은 건너 뛰고 아래의 map[nums[i]] = i라는 라인을 설명하자면, map이라는 object에 key값이 nums[i]인 원소는 i라는 인덱스를 그대로 저장하게 두었습니다.

그리고 다음 루프를 돌게 됩니다. 이번에 nums[i]의 값은 다음 인덱스의 값인 7이 들어오게 되고, target은 여전히 2입니다.

이번 루프에서 또 another를 계산하게 됩니다. another 내부에는 target - nums[i] 연산을 수행한 결과인 2가 들어오게 됩니다. 여기서 우리가 생각해봐야 할 것은 지금 나온 값인 이 2를 보충할 수 있게 된다면, 총 합이 target인 두 숫자를 구할 수 있게 된다는 것입니다.

그래서 보충할 숫자를 아까 숫자에 해당하는 인덱스를 맵핑했던 map Object에서 찾아내고, 두 개의 인덱스를 정답으로 리턴하는 문제이니 [map[another], i]를 그대로 정답으로 리턴합니다.

배운 점

우리가 배열과 같은 값을 탐색할 때, 그 과정이 map으로 해결될 수 있는 건 아닌지 다시한번 생각해 보아야 하는 것 같습니다.

이 경우에는 우리가 앞서 지나왔던 특정 값들을 map에 기억함으로써, 루프 하나를 줄였습니다.

또한 매번 생각해야 할 것은 현재 값과 앞에 계산했던 특정 계산 값을 이용하여 값이 완성될 수 있다면, memoization처럼 앞서 계산한 혹은 앞서 가지고 있던 값을 버리지 말고 특정 저장소에 저장해두었다가 활용할 수 있다는 것도요.

이 모범답안에서는 for문으로 탐색하는 대신 시간복잡도를 최소화하기 위해 map에 보충해야 할 key값을 저장해두었다가 그대로 활용합니다.