1. Two Sum

LeetCode 1번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

Two Sum - LeetCode

풀이 1

아이디어

단순하게 nums를 순회하면서 현재 원소(num)과 합해서 target을 만들 수 있는 원소가 있는지 확인한다.

코드

function twoSum1(nums: number[], target: number): number[] {
  for (let idx = 0; idx < nums.length - 1; idx++) {
    const complementIdx = nums.indexOf(target - nums[idx], idx + 1);
    if (complementIdx !== -1) {
      return [idx, complementIdx];
    }
  }
  // 타입 에러를 제거하기 위해 추가한 코드.
  // 답이 무조건 존재한다는 조건이 있었으므로 이 코드에는 도달하지 않는다.
  return [];
}

시간 / 공간 복잡도

• 시간 복잡도: nums를 순회하면서 (O(n)) Array.indexOf 메소드로 짝이 되는 원소를 찾는 방식 (O(n)) O(n)이 중첩되어 있으므로 O(n²)
• 공간 복잡도: 답을 제외하면 추가로 필요한 공간이 없으므로 O(1)

풀이 2

아이디어

O(n)보다 작게 만들 수 있는 방법은 인덱스를 찾는 데 걸리는 시간을 줄이는 것이라 생각해서 검색 시간이 짧은 Map을 활용했다. Map인 이유는 index도 함께 저장해야 하기 때문…

nums의 원소를 key로, 그 index를 value로 하는 Map을 미리 만들어두고 시작했다.

코드

function twoSum2(nums: number[], target: number): number[] {
  const numMap = nums.reduce((map, num, idx) => {
    map.set(num, idx);
    return map;
  }, new Map());

  for (let idx = 0; idx < nums.length; idx++) {
    const complementIdx = numMap.get(target - nums[idx]);
    if (complementIdx !== undefined && complementIdx !== idx) {
      return [idx, complementIdx];
    }
  }

  return [];
}

시간 / 공간 복잡도

• 시간 복잡도: Map을 생성할 때 O(n), Map에서 짝이 되는 원소를 찾는 것은 O(1)이므로 O(n)
• 공간 복잡도: Map을 생성할 때 n만큼의 공간이 추가로 필요하므로 O(n)

풀이 3

아이디어

짝을 찾는 for loop에서 Map에서 찾은 원소가 현재 원소와 동일한 것인지를 확인하는 조건문이 마음에 들지 않아서 좀 더 좋은 방법이 있는지 찾아보다 발견한 방법. Map을 미리 생성하지 않고 짝을 찾는 for loop에서 Map을 생성한다.

[a, b]가 답일 때 지금까지는 a를 기준으로 b를 찾았지만 지금은 b를 기준으로 a를 찾게 되는 것! 원소의 짝을 찾을 때 현재 원소를 Map에 추가하기 전이기 때문에 맘에 들지 않던 조건문도 안 써도 된다.

코드

function twoSum3(nums: number[], target: number): number[] {
  const numMap = new Map();

  for (let idx = 0; idx < nums.length; idx++) {
    const complementIdx = numMap.get(target - nums[idx]);
    if (complementIdx !== undefined) {
      return [idx, complementIdx];
    }
    numMap.set(nums[idx], idx);
  }

  return [];
}

시간 / 공간 복잡도

• 시간 복잡도: 풀이 2와 동일하게 O(n)
• 공간 복잡도: 풀이 2와 동일하게 O(n) (단, 조금 메모리를 덜 쓴다)