Sum of pairs

September 12th 2018

Sum of pairs (자바스크립트)

문제 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.

첫 번째 인수로 주어진 배열의 각 요소의 합이, 두 번째 인수로 주어진 수와 일치하는 숫자 쌍을 찾아 반환해야 하는 알고리즘입니다. 여러개의 쌍을 발결하면 두 요소간의 인덱스 간격이 더 적은 pair를 반환해야 합니다. 또한, 인덱스 간격이 같다면 배열의 앞쪽에 위치한 pair를 반환해야 합니다.

풀이 방법을 생각해보면 간단해 보입니다. 하지만, 코드로 풀이를 구현하기는 쉽지 않은 것 같습니다.

- 먼저 인수로 주인진 배열을 loop를 돌아 합이, 주어진 수와(두 번째 인수) 일치하는 pair를 찾습니다. - 찾은 pair의 두 수, pair의 인덱스 간격을 배열로 저장합니다. - loop를 돌며 또다른 pair를 찾은 경우, 기존 pair의 인덱스 간격과 비교를 해 더 낮은 pair를 저장합니다. - 마지막에 남은 pair를 반환합니다.

처음에 위와 같은 풀이로 문제를 풀었습니다.

난관봉착 저는 저의 주 무기(...?)인 이중 loop를 쓰며 호기롭게 문제를 풀어나갔습니다. 하지만, 긴 데이터가 들어왔을 때 여느 때와 마찬가지로 time performance에서 고배를 마셨습니다. pair의 두 수와 인덱스의 간격을 한 배열에 저장하는 것도 뭔가 깔끔하지 못한 느낌이 들었습니다.

time performance에 pass 하기 위해서는 loop를 한 번만 돌며 문제를 해결해야 했습니다. 처음에 사용했던 indexOf method도 어찌 됐든 loop를 여러 번 도는 것이기 때문에 사용할 수 없었습니다. 결론적으로는 아래와 같이 해당 알고리즘을 풀이했습니다.

- loop를 돌며 마주치는 숫자와 pair가 가능한 수를 object에 저장합니다. - 새로 마주친 수가 기존에 봤던 수와 pair가 가능한지 확인합니다. - pair가 가능하고 기존에 찾은 다른 pair가 있다면, 기존 pair의 인덱스 간격과 비교를 해 더 낮은 pair를 저장합니다. - 그렇지 않으면 새로 찾은 pair를 저장합니다.

위와 같이 memorization 사용을 해 중복 loop를 피하고, time performance를 pass 할 수 있었습니다.

var sum_pairs = function(ints, s) {
  var result = {};
  var memo = {};

  for (var i = 0; i < ints.length; i++) {
    if (memo.hasOwnProperty(ints[i])) {
      var newpair = {
        interval: i - memo[ints[i]].index,
        pair: [memo[ints[i]].prevNum, ints[i]]
      };

      if (result.interval > newpair.interval) {
        result = newpair;
      }
    } else {
      var need = s - ints[i];
      memo[need] = {
        prevNum: ints[i],
        index: i
      };
    }
  }

  return result.pair;
};

아래는 제가 작성한 코드와 맥락은 같으나, 매우 간결하게 코딩을 해서 참고차 가져와 봤습니다. 알고는 있지만, 아래 코드를 보니 저는 아직 갈 길이 한 참 멀었네요.. 그런데 아래 코드를 읽다 보니, pair가 두 개 이상일 때 그 간격을 비교하는 내용은 빠진것 같습니다. 만약 배열 뒤쪽에 기존의 배열보다 간격이 더 짤은 pair가 있다면 문제가 될 것 같습니다. 아니면 제가 문제 조건의 우선순위를 잘 못 이해한 것 같습니다.

var sum_pairs = function(ints, s) {
  var seen = {};
  for (var i = 0; i < ints.length; i++) {
    if (seen[s - ints[i]]) {
      return [s - ints[i], ints[i]];
    }
    seen[ints[i]] = true;
  }
};

// sum_pairs([10, 5, 2, 5, 3, 7], 10)
// = > [3, 7]을 반환해야 하지만 [5, 5]를 반환합니다.

Handmade with .