효율적인 중복제거 방법

두 개 뽑아서 더하기

function solution(numbers) {
  const answer = [];
  for (let i = 0; i < numbers.length - 1; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      const sum = numbers[i] + numbers[j];
      if (answer.indexOf(sum) == -1) {
        answer.push(sum);
      }
    }
  }
  answer.sort((a, b) => a - b);
  return answer;
}

중복제거 방법

1. Set()

// 내부적으로 해시 테이블을 사용하여 요소를 저장해 검색 속도가 빠름
// 따라서 중복되는 인덱스를 바로 찾을 수 있음

const test1 = () => {
  const arr = [1, 2, 2, 3];
  const result = [...new Set(arr)]
  return result
}

2. filter, indexOf

// 각 요소마다 중복 여부를 확인하기 위해 반복 검색을 수행함
const test2 = () => {
  const arr = [1, 2, 2, 3];
  const result = arr.filter((v, i) => arr.indexOf(v) === i)
  return result
}

Set이 더 빠른 이유는 상수 시간 복잡도를 가진다?

선형 시간 복잡도(Linear Time Complexity):

선형 시간 복잡도는 입력 크기에 따라 알고리즘의 실행 시간이 선형적으로 증가하는 경우를 말합니다. 즉, 입력 크기가 n이라면, 알고리즘의 실행 시간은 대략적으로 O(n)의 시간이 소요됩니다. 예를 들어, 배열의 각 요소를 순회하며 특정 연산을 수행하는 경우, 입력 배열의 크기에 비례하여 실행 시간이 증가합니다.

상수 시간 복잡도(Constant Time Complexity):

상수 시간 복잡도는 입력 크기에 관계없이 알고리즘의 실행 시간이 일정한 경우를 말합니다. 즉, 입력 크기가 변하더라도 실행 시간은 변하지 않고 일정한 시간이 소요됩니다. 상수 시간 복잡도를 갖는 알고리즘은 입력 크기에 관계없이 동일한 수행 시간을 보장합니다. 예를 들어, 배열의 첫 번째 요소를 찾는 작업이나, 상수 개수의 연산을 수행하는 작업은 상수 시간 복잡도를 가집니다. 이는 실행 시간이 입력 크기에 영향을 받지 않기 때문에 매우 효율적인 알고리즘이라고 할 수 있습니다.

문제 리팩토링

const solution = (numbers) => {
  const answer = [];
  for (let i = 0; i < numbers.length - 1; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      const sum = numbers[i] + numbers[j];
        answer.push(sum);
    }
  }
  return [...new Set(answer)].sort((a, b) => a - b);
}