[Javascript] 두 개의 수로 특정 값 만들기

문제

n개의 양의 정수로 이루어진 리스트 arr와 정수 target에 주어졌을 때 이 중에서 합이 target인 두 수가 arr에 있는지 찾고, 있으면 true, 없으면 false를 반환하는 solution() 함수를 작성하세요.

제약 조건

• n은 2 이상 10,000 이하의 자연수입니다.
• arr의 각 원소는 1 이상 10,000 이하의 자연수입니다.
• arr의 원소 중 중복되는 원소는 없습니다.
• target은 1 이상 20,000 이하의 자연수입니다.

입출력 예시

arr	target	return
[1, 2, 3, 4, 5]	6	True
[2, 3, 5, 9]	10	False

 

해당 문제를 보면 바로 떠올릴수 있는 방법은 각 원소에 대해 다른 원소들을 각각 더해보며 target을 만족시키는 경우를 찾는 방법입니다. 하지만 이 방법은 시간복잡도가 O(N²)으로, 데이터가 많아질수록 효율성이 떨어집니다.

 

나의 풀이

• 시간복잡도: O(N)

function solution(arr, target) {
    const complementMap = {};

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

        if (complement in complementMap) {
            return true;
        }

        complementMap[arr[i]] = i;
    }

    return false;
}

배열을 순회하면서 각 원소에 대해 목표 합에서 현재 원소를 뺀 값(보수)이 이미 해시 테이블에 존재하는지 확인하고, 존재하지 않으면 현재 원소를 해시 테이블에 추가합니다.

complementMap[arr[i]] = true; 로 저장해도 동일하게 작동하지만, 코드의 확장성을 고려하여 인덱스를 저장

 

다른 풀이

위의 코드를 Map을 이용해서도 동일하게 구현 가능합니다.

function solution(arr, target) {
    const complementMap = new Map();

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

        if (complementMap.has(complement)) {
            return true;
        }

        complementMap.set(arr[i], i);
    }

    return false;
}

 

다음과 같이 계수 정렬 알고리즘을 사용해서도 해결할 수 있습니다.

• 시간복잡도: O(N + K)

function countSort(arr, k) {
  // ➊ 해시 테이블 생성 및 초기화
  const hashtable = new Array(k + 1).fill(0);
  for (const num of arr) {
    // 현재 원소의 값이 k 이하인 때에만 처리
    if (num <= k) {
      // 현재 원소의 값을 인덱스로 해 해당 인덱스의 해시 테이블 값을 1로 설정
      hashtable[num] = 1;
    }
  }

  return hashtable;
}

function solution(arr, target) {
  const hashtable = countSort(arr, target);
  for (const num of arr) {
    const complement = target - num;
    // ➋ target에서 현재 원소를 뺀 값이 해시 테이블에 있는지 확인
    if (
      complement !== num &&
      complement >= 0 &&
      complement <= target &&
      hashtable[complement] === 1
    ) {
      return true;
    }
  }

  return false;
}

 

---

Reference

코딩테스트 합격자되기: 자바스크립트 편