essential
essential

3. PickTwoAddMore

숫자배열에서 서로 다른 두 수를 더해서 오름차순 정렬하기

algorithm test

03. PickTwoAddMore

Sunhyup Lee. (2024). To be a successful candidate for the coding test. goldenrabbit. p.115.


Problem solving

숫자 배열에서 서로 다른 두 수를 선택해서 더한 결과를 모두 구하고 오름차순으로 정렬해서 반환하자 허나, 중복값은 허용하지 않는다.


① The first way to solve the problem : for문 이용해서 풀기

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

🧐 시간복잡도는 어떨까?

[Done] exited with code=0 in 0.06 seconds

1) 이중루프: O(n2)
2) 중복 제거 및 정렬: O(n2 log n)

최종 시간 복잡도: O(n2 log n))



② The second way to solve the problem : 배열의 모든 쌍을 미리 계산 후 중복 제거 및 정렬

function solution(numbers) {
  const ret = [];
  numbers.forEach((num1, index1) => {
    numbers.slice(index1 + 1).forEach(num2 => {
      ret.push(num1 + num2);
    });
  });
  return [...new Set(ret)].sort((a, b) => a - b);
}

🧐 시간복잡도는 어떨까?

[Done] exited with code=0 in 0.062 seconds

1) 이중 forEach 루프: O(n2)
2) 중복제거 및 정렬: O(n2 log n) 소요

최종 시간 복잡도: O(n2 log n))



③ The third way to solve the problem : 재귀적 접근

function solution(numbers) {
  function combine(nums, start, result) {
    if (start >= nums.length) return;
    for (let i = start + 1; i < nums.length; i++) {
      result.add(nums[start] + nums[i]);
    }
    combine(nums, start + 1, result);
  }

  const result = new Set();
  combine(numbers, 0, result);
  return Array.from(result).sort((a, b) => a - b);
}

🧐 시간복잡도는 어떨까?

[Done] exited with code=0 in 0.067 seconds

1) 재귀 호출과 이중 for 루프: O(n2)
2) 중복제거 및 정렬: O(n2 log n) 소요

최종 시간 복잡도: O(n2 log n))



④ The fourth way to solve the problem : Map을 사용한 접근

function solution(numbers) {
  const sumMap = new Map();
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      const sum = numbers[i] + numbers[j];
      sumMap.set(sum, true);
    }
  }
  return Array.from(sumMap.keys()).sort((a, b) => a - b);
}

🧐 시간복잡도는 어떨까?

[Done] exited with code=0 in 0.071 seconds

1) 이중 루프와 Map 저장: O(n2)
2) 중복제거 및 정렬: O(n2 log n) 소요

최종 시간 복잡도: O(n2 log n))



⑤ The fifth way to solve the problem : 배열 메서드를 활용한 함수형 접근

function solution(numbers) {
  return numbers.flatMap((num, i) => 
    numbers.slice(i + 1).map(num2 => num + num2)
  )
  .filter((val, index, self) => self.indexOf(val) === index)
  .sort((a, b) => a - b);
}

🧐 시간복잡도는 어떨까?

[Done] exited with code=0 in 0.068 seconds

1) flatMap 및 slice: O(n2)
2) filter를 통한 중복 제거: O(n3)
3) 정렬: O(n2 log n)

최종 시간 복잡도: O(n3)



⑥ The sixth way to solve the problem : 직접 인덱스 쌍을 만들어서 접근

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

🧐 시간복잡도는 어떨까?

[Done] exited with code=0 in 0.095 seconds

1) 이중루프: O(n2)
2) 중복제거: O(n2)
3) 정렬: O (n2 log n)

최종 시간 복잡도: O(n log n) + O(n) = O(n2 log n)



Development
Algorithm