448. Find All Numbers Disappeared in an Array

리트코드 448번 풀이

문제

Find All Numbers Disappeared in an Array

풀이 1

아이디어

배열을 Set으로 변환한 뒤, 1부터 n까지 순회하면서 Set에 없는 숫자를 결과에 추가한다.

코드

function findDisappearedNumbers(nums: number[]): number[] {
  const numSet = new Set(nums);
  const n = nums.length;
  const ret: number[] = [];

  for (let num = 1; num <= n; num++) {
    if (!numSet.has(num)) ret.push(num);
  }

  return ret;
}

시간 / 공간 복잡도

• 시간 복잡도: O(n)
• 공간 복잡도: O(n) — Set 저장 공간

풀이 2

아이디어

Leetcode의 도발에 넘어가 추가로 고민해본 풀이… (개인적으론 좀 억지로 푼 것 같다는 생각을 버릴 수 없다.)

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

이 풀이에서는 배열 자체를 방문 표시판으로 활용한다. 숫자 num이 존재하면 인덱스 num - 1의 값을 음수로 표시하고, 마지막에 양수로 남아있는 인덱스가 빠진 숫자다.

추가 공간을 사용하지 않는다는 장점이 있지만, 원본 배열을 변경한다는 단점이 있다. 문제에서 허용하긴 했지만 side effect가 발생할 수 있으므로 상황에 따라 풀이 1이 더 나을 수 있다.

코드

function findDisappearedNumbers(nums: number[]): number[] {
  for (const num of nums) {
    const idx = Math.abs(num) - 1;
    if (nums[idx] > 0) nums[idx] *= -1;
  }

  const ret: number[] = [];
  for (let idx = 0; idx < nums.length; idx++) {
    if (nums[idx] > 0) ret.push(idx + 1);
  }
  return ret;
}

시간 / 공간 복잡도

• 시간 복잡도: O(n)
• 공간 복잡도: O(1) — 반환값 제외, 입력 배열만 사용