1. Two Sum

💡 풀이

// O(NlogN)
var twoSum = function (nums, target) {
  let sorted = [...nums].sort((a, b) => a - b);

  let end = sorted.length - 1;
  let start = 0;
  let answer = [];

  for (let i = 0; i < sorted.length; i++) {
    if (sorted[start] + sorted[end] > target) {
      end--;
    } else if (sorted[start] + sorted[end] === target) {
      answer = [sorted[start], sorted[end]];
    } else {
      start++;
    }
  }

  answer = [nums.indexOf(answer[0]), nums.lastIndexOf(answer[1])];

  return answer;
};

// O(N)
var twoSum = function (nums, target) {
  let hash = {};

  for (let i = 0; i < nums.length; i++) {
    const n = nums[i];
    if (hash[target - n] !== undefined) {
      return [hash[target - n], i];
    }
    hash[n] = i;
  }
  return [];
};

let nums = [3, 3];
let target = 6;
twoSum(nums, target);

📝 정리

맨 처음 leetcode 문제를 풀었을 때 접했던 문제였다. 당시에는 반복문을 두 개 사용해서 O(N*N)의 시간 복잡도(Brute Force)로 문제를 해결했었다. 그 때는 시간 복잡도에 대한 개념도 자세히 안 잡혀있었고.. 단순히 문제를 풀어냈다는 사실 자체가 좋았었다..!

아무튼 요점은, 이 문제의 Follow up에는 시간 복잡도를 O(N*N)보다 낮게 풀 수 있는지를 물어본다. 이번엔 그 방법에 대해 생각을 해봤다.

1. 먼저 처음 내가 푼 방법이다. 시간 복잡도 O(NlogN)으로 풀었던 방법이다. Two pointer를 사용했다.

• nums 배열을 먼저 정렬을 한다. 이 때 시간 복잡도가 O(NlogN)이 나오게 된다. 이후 포인터 두개를 사용해서 정렬한 nums 배열(이하 sorted)에서 sorted[start] + sorted[end]의 합계에 따라 분기 처리를 해주고, 그 합이 target 보다 크면 end 포인터를 한 칸씩 앞으로 옮기고, 반대의 경우에는 start 포인터를 한 칸씩 앞으로 옮겨준다. 그러다 target과 합계가 같은 순간이 오면 두 요소의 원래 nums 배열에서의 index가 답이 된다.

2. 두 번째는 시간 복잡도 O(N)의 방법이다. Hash map을 사용한다.

• 먼저, hash라는 객체를 하나 만들어주고, 반복문을 돌며 만약 hash[target-n]이 이미 hash 객체 안에 존재한다면?

• 그게 바로 정답이 된다는 뜻이니 해당 loop을 돌 때의 index와 hash[target-n]이 정답이 된다.

수정, 지적을 환영합니다!

문제 링크

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

LeetCode GitHub

https://github.com/tTab1204/LeetCode