유데미 알고리즘 강의를 1차로 다 듣고 LeetCode에서 Top Interview Questions를 풀면서 연습하고 있는데 easy 단계부터 시작하면 하루에 3-5문제 금방 풀 수 있을 줄 알았지만 생각보다 오래 걸려서 자괴감 박박.... 그래도 배운 자료 구조 적용하면서 코드 개선할 때 좀 재미있다. 적응하면 속도 좀 붙겠지 ? 제발요... 🤯

💻 Two Sum Question

📝 문제 설명

정수가 담긴 배열 nums와 정수 target을 두 인자로 받으며 nums의 요소 두 개를 더했을 때 target과 같아야 하는데 이 두 요소의 index를 배열로 반환하는 함수 twoSum을 작성하세요. (하나의 input은 하나의 결괏값만 가져야 하며, 반환되는 요소의 순서는 상관X)

첫 코드

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

⌛ 시간 복잡도 : O(n^2)

역시 바로 생각나는 방법은 중첩 반복문을 돌리는 코드였다. 그리고 처음에는 생각 없이 빈 배열 result를 전역으로 선언했는데 이렇게 하면 테스트 할 때마다 이전 결과가 들어있어서 바로 함수 안에 지역 변수로 바꿨다. 확실한 이유가 없으면 전역 변수를 지향하라는 말이 생각났다. 쉬운 방법이긴 했지만 O(n^2) 시간 복잡도를 갖는 알고리즘은 너무 비효율적이기 때문에 해쉬 테이블을 사용하고 반복문을 한 번만 돌리는 방법을 생각해보았다.

개선 코드

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

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

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

    hash[nums[i]] = i;
  }

  return null;
};

⌛ 시간 복잡도 : O(n)

hash라는 변수에 빈 객체를 할당하고 반복문을 돌며 key는 nums의 각 요소로, value는 인덱스로 넣고 nums[i]에 더해져야 하는 another가 이미 hash에 있다면 순회 당시의 index와 저장되어 있는 value(another의 인덱스 = hash[another])를 배열에 담아 반환한다.

이렇게 중첩 반목문의 비효율성을 개선하기 위해 객체를 활용하는 경우가 정말 정말 많다고 한다. 아직 그렇게 익숙하지는 않아서 연습을 많이 해봐야할 것 같다 ✊🏻👊🏻