[알고리즘/자바스크립트] 더해서 특정 숫자가 나오는 한 쌍 찾기 (Sum of Pairs)

-해당 문제는 codewars사이트의 level5 문제입니다. (1~8단계 중 8단계가 가장 쉬운 레벨)-

 

[문제] Given a list of integers and a single sum value, return the first two values (parse from the left please) in order of appearance that add up to form the sum.

sum_pairs([11, 3, 7, 5],         10)
#              ^--^      3 + 7 = 10
== [3, 7]

sum_pairs([4, 3, 2, 3, 4],         6)
#          ^-----^         4 + 2 = 6, indices: 0, 2 *
#             ^-----^      3 + 3 = 6, indices: 1, 3
#                ^-----^   2 + 4 = 6, indices: 2, 4
#  * entire pair is earlier, and therefore is the correct answer
== [4, 2]

sum_pairs([0, 0, -2, 3], 2)
#  there are no pairs of values that can be added to produce 2.
== None/nil/undefined (Based on the language)

sum_pairs([10, 5, 2, 3, 7, 5],         10)
#              ^-----------^   5 + 5 = 10, indices: 1, 5
#                    ^--^      3 + 7 = 10, indices: 3, 4 *
#  * entire pair is earlier, and therefore is the correct answer
== [3, 7]

Negative numbers and duplicate numbers can and will appear.

NOTE: There will also be lists tested of lengths upwards of 10,000,000 elements. Be sure your code doesn't time out.

 

[문제 해석] 숫자들의 목록 배열과 숫자값이 주어질 것이다. 왼쪽부터 파싱했을 때, 더해서 주어진 숫자값이 나오는 숫자 2개를 찾아서 배열로 리턴해라. 만약에 여러 쌍의 숫자가 있을 경우엔 마지막 숫자의 인덱스 번호가 가장 작은 쌍이 답이 된다. 음수와 복수값이 존재할 수 있다.

주의할 점: 10,000,000개에 가까운 요소들이 테스트 배열로 주어질 것이다. 시간이 초과되지 않도록 주의하여라.

 

 

---

 

 

 

내가 처음 생각한 로직은 이렇다.

 

위 배열을 예시로 들면 두 숫자를 더해서 10이 되는 숫자를 찾아야하므로

일단 배열을 왼쪽부터 순회하면서 해당 숫자를 10에서 뺀다.

 

그리고 그 뺀값을 해당 숫자 다음 인덱스부터 검색해서

못 찾으면 다음으로 패스하고 찾으면 해당 숫자를 배열에 저장한다.

 

만약에 또 다른 숫자 쌍을 발견하면 마지막 숫자의 인덱스가 작은 쪽으로 저장한다.

 

 

var sum_pairs = function (ints, s) {
  let findN;
  let hasN;
  let result;

  for (let i = 0; i < ints.length; i++) {
    findN = s - ints[i];
    let search = ints.indexOf(findN, i + 1);
    if (search !== -1) {
      if (! hasN || hasN > search) {
        hasN = search;
      }
      result = [ints[i], ints[hasN]];
      ints.splice(search + 1);
    }
  }
  return result;
}

 

위 로직대로 코드로 쓰고 테스트를 돌렸더니 샘플 테스트는 통과하였으나

완전 긴 배열로 된 테스트는 시간초과로 통과되지 못했다. 흑흑..ㅠㅠ

 

 

 

그니까 로직은 맞는데, 시간이 댑따 오래 걸린다는 뜻이니

다시 코드를 살펴보면서 시간을 단축시킬 수 있는 방법이 없을지 고민해보았다.

 

 

var sum_pairs = function (ints, s) {
  let findN;
  let hasN;
  let result;
  let noneArr = [];

  for (let i = 0; i < ints.length; i++) {
    if (noneArr.find((e) => e === ints[i])) {
      continue;
    }
    findN = s - ints[i];
    let search = ints.indexOf(findN, i + 1);
    if (search === -1) {
      noneArr.push(ints[i]);
    } else {
      if (! hasN || hasN > search) {
        hasN = search;
      }
      result = [ints[i], ints[hasN]];
      ints.splice(search + 1);
    }
  }
  return result;
}

 

1. 일단 처음으로 숫자 한 쌍을 찾으면 그 숫자 한 쌍 바로 다음부터 나오는 배열 요소를 모두 제거하여 탐색 범위를 축소한다.

 

2. 찾는 값이 없는 숫자는 noneArr이란 배열에 저장한 후에 다음부터 탐색할 때, noneArr 배열에 있는 중복값이면 탐색을 패스한다.

 

 

이젠 또 다른 이슈로 에러가 발생했다. ㅜㅜ...

계속 코드를 봐도 이유를 모르겠어서 바닐라코딩 준모님에게 SOS를 요청했다.

 

 

일단 내 코드에서 잘못된 점이 find() 메소드를 통해 중복 수를 검사했던 것. find() 메소드를 돌렸을 때 만약에 숫자 0이 출력되면 falsy값이 되어 의도치 않게 false가 되기 때문이다.

 

그리고 splice() 메소드가 원본 배열 자체를 바꾸는 메소드인데, 원본 배열을 조작하는 메소드의 경우에 알고리즘 문제를 풀 때 성능이 안 좋아진다고 한다(!) 전혀 모르고 splice()를 여기저기에 마구 사용했던 과거가 주마등처럼 스쳐지나갔다. 

 

 

var sum_pairs = function (ints, s) {
  let findN;
  let hasN;
  let result;
  let noneArr = [];
  let copiedAr = ints;
  let end = copiedAr.length;

  for (let i = 0; i < end - 1; i++) {
    let evaluate = noneArr.find((e) => e === ints[i]);
    if (evaluate !== undefined) {
      continue;
    }
    findN = s - ints[i];
    let search = copiedAr.indexOf(findN, i + 1);
    noneArr.push(ints[i]);
    if (search !== -1) {
      if (! hasN || hasN > search) {
        hasN = search;
      }
      result = [ints[i], ints[hasN]];
      end = search + 1;
      copiedAr = ints.slice(0, search + 1);
    }
  }
  return result;
}

 

1. splice() 메소드를 사용하지 않고 slice()를 사용하였고, for문의 조건절을 수정하여 범위를 좁혀주었다.

(그리고 배열의 마지막 수도 어차피 순회할 이유가 없으므로 순회 범위에서 빼주었다.)

 

2. find() 메소드로 중복 수를 검사하는 방법을 수정하였다.

 

3. 중복 수의 범위를 늘렸다. 한 번 찾은 숫자 또한 중복 수로 검색되게끔 했다.

 

 

 

 

통과 완료!