LeetCode 1. Two Sum

알고리즘 면접 대비용으로 작성하는 시리즈!

 

목표:

두가지 이상의 풀이방법을 구현하고 설명하기

시간/공간 복잡도를 나타내기

왜 이 풀이가 저 풀이보다 성능이 나은지 논리적으로 설명하기

면접질문에 대답한다고 생각하고, 핵심을 설명하되 말을 너무 길게 하지 않기 (개인적으로는 세 문장이 적절하다고 생각)

분명하고 적절한 용어를 사용해서 설명하기

 

---

 

질문:

LeetCode 문제

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.

+ 항상 답이 있다고 가정한다.

 

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]

 

 

 

Solution 1

Brute force

var twoSum = function(nums, target) {
  for (let i = 0; i<nums.length-1; i++){
    for (let j = i+1; j<nums.length; j++){
      if (nums[i]+nums[j] === target)
        return [i,j];
    }
  }
};

· 배열의 특정 i번째 원소를 피봇으로 잡고, 이후의 원소들을 순회하면서 nums[i]+nums[j]가 target과 같은지 찾는다.

 

· 시간복잡도/공간복잡도: O(n^2)/O(1)

최대 두 번의 loop문을 돌 수있기 때문에 시간복잡도는 O(n^2)이며, i와 j의 값만 메모리에 저장하기 때문에 공간복잡도는 O(1)이다.

 

 

 

 

🧐 다른 방법으로 풀 수 있나요?

 

 

 

 

Solution 2

input으로 받은 배열을 변경한 뒤, 왼쪽 피봇과 오른쪽 피봇을 조건에 따라 순차적으로 옮겨가며 순회

var twoSum = function(nums, target) {
    let leftIdx = 0;
    let rightIdx = nums.length - 1;
    const copyNums = [...nums].sort((x,y) => x-y);

    while (leftIdx < rightIdx){
        const sum = copyNums[leftIdx] + copyNums[rightIdx];
        if (sum > target){
            rightIdx--;
        } 
        else if (sum < target) {
            leftIdx++;
        } else {
            const firstIdx = nums.indexOf(copyNums[leftIdx]);
            nums[firstIdx] = null;
            const secondIdx = nums.indexOf(copyNums[rightIdx])
            return [firstIdx, secondIdx];
        }
    }
};

· 원본 배열을 유지하기 위해 copyNums라는 배열을 새로 생성하여 오름차순 정렬한 뒤 왼쪽, 오른쪽에 피봇을 하나씩 둔다. (leftIdx, rightIdx)

🤔 주의! js에서 sort를 하면 우리가 원하는 모양이 나오지 않는 경우가 있다. (sort 시켜놨더니 [10, 100, 11]로 나오는 경우를 봤을것이다) 따라서 compare 함수를 넣어준다.

· copyNums[leftIdx]+copyNums[rightIdx]의 값을 확인하여 target보다 큰 경우, rightIdx를 한 칸 앞으로 이동한다. (그렇게 해야 결과값이 작아지기 때문이다)

· 더한 값이 target보다 작은 경우, leftIdx를 한 칸 뒤로 이동한다. (그렇게 해야 결과값이 커지기 때문이다)

· 만약 target과 같은 경우, 원본 배열인 nums에서 copyNums[leftIdx]와 copyNums[rightIdx] 값이 어느 index를 가졌는지 확인한다.

🤔 엣지 케이스! input으로 들어온 배열이 [3,3]인 경우 indexOf를 사용하면 같은 index를 반환하기 때문에 한번 찾은 index의 값은 null처리를 해준다.

 

· 시간복잡도/공간복잡도: O(n^2)/O(n)

while문에서 최대 1/2n번 순회하고, nums.indexOf에서 O(n)의 시간복잡도를 가지기 때문에, 전체 코드의 시간복잡도는 O(n^2)가 된다.

copyNums 배열을 새로 생성하여 활용하기 때문에 공간복잡도는 O(n)이 된다.

 

🌱 추가학습! js의 내장함수 Array.prototypes.sort에 대해 알아보기

· js에서 sort하면 Firefox에서는 merge sort, Chrome에서는 tim sort 라는 방식을 사용한다.

크로미움 기반 웹 브라우저(크롬, 오페라, 엣지..)들은 V8엔진을 사용하는데, V8엔진은 Timsort를 사용하고, Firefox는 Gecko엔진을 사용하기 때문이다.

· merge sort는 O(n logn)의 시간복잡도를 가진다.

· Timsort는 merge sort와 insertion sort를 합친 구조로, O(n logn)의 시간복잡도를 가진다.

 

 

 

 

🧐 Solution2보다 성능을 향상시킬 수 있는 방법이 있을까? 생각해보자.

 

 

 

 

Solution3

Hashmap을 사용, 두 숫자 중에 하나는 target - nums[i]라는 점에서 착안

var twoSum = function(nums, target) {
    let hashmap = {};
    for (let i = 0; i<nums.length; i++){
        const val = target - nums[i];
        if (val in hashmap){
            return [hashmap[val], i];
        }
        else {
            hashmap[nums[i]] = i;
        }
    }
};

· 배열 nums를 순회하며, 우리가 찾는 값이 hashmap에 없는 경우 저장한다. key는 nums배열의 값, value는 nums배열의 index로 설정해서 hashmap에 key를 넣으면 우리가 원하는 nums배열의 index가 튀어나오도록 한다.

· 우리가 찾는 값이 hashmap에 있는 경우, 바로 답을 얻을 수 있게 된다.

 

· 시간복잡도 / 공간복잡도: O(n) / O(n)

for문 순회 한 번으로 시간복잡도는 O(n)이고, hashmap을 사용하기 때문에 공간복잡도는 O(n)이 된다.

 

 

 

Reference

· https://stackoverflow.com/questions/57763205/what-is-array-prototype-sort-time-complexity