Sum of intervals

January 13th 2019

Sum of intervals

Write a function called sumIntervals that accepts an array of intervals, and returns the sum of all the interval lengths. Overlapping intervals should only be counted once.

Intervals Intervals are represented by a pair of integers in the form of an array. The first value of the interval will always be less than the second value. Interval example: [1, 5] is an interval from 1 to 5. The length of this interval is 4.

Overlapping Intervals

List containing overlapping intervals:

[ [1,4], [7, 10], [3, 5] ]

The sum of the lengths of these intervals is 7. Since [1, 4] and [3, 5] overlap, we can treat the interval as [1, 5], which has a length of 4.

Examples: sumIntervals( [ [1,2], [6, 10], [11, 15] ] ); // => 9 sumIntervals( [ [1,4], [7, 10], [3, 5] ] ); // => 7 sumIntervals( [ [1,5], [10, 20], [1, 6], [16, 19], [5, 11]] ); // => 19

문제 자체는 간단합니다. 배열을 요소로 가지고 있는 배열이 인자로 주어지고 각 배열 요소의 숫자 간격의 합을 구하는 것입니다. 배열 요소의 숫자가 겹치는 경우는 중복해서 계산을 하면 안 됩니다. codewars의 4 kyu 문제이지만, 제 주위 친구들은 이 문제를 비교적 쉽고 빠르고 잘 풀었습니다. 하지만 저는 시간도 매우 많이 걸리고 문제 풀이도 매우 길고 엉망이었습니다. 그래서 이곳에 풀이를 옮겨 놓는 것도 창피하지만 글을 쓰기 위해 코드를 가져왔습니다.

function sumIntervals(intervals) {
  const arr = intervals.slice();
  const result = [arr[0]];
  let overlapped = false;

  for (let i = 1; i < arr.length; i++) {
    const newLow = arr[i][0];
    const newHigh = arr[i][1];

    for (let j = 0; j < result.length; j++) {
      const curLow = result[j][0];
      const curTop = result[j][1];

      if (curLow <= newLow && newHigh <= curTop) {
        overlapped = true;
        break;
      } else if (curLow <= newLow && curTop < newHigh) {
        if (result[j + 1]) {
          if (newHigh < result[j + 1][0]) {
            result[j][1] = newHigh;
          } else if (newHigh >= result[i + 1][0] && newHigh <= result[i + 1][1]) {
            result[j][1] = result[j + 1][1];
            result.splice(j + 1, 1);
          }

          overlapped = true;
          break;
        }
      }
    }

    if (!overlapped) {
      result.push(arr[i]);
    }
  }

  return result.reduce((acc, cur) => {
    return acc + (cur[1] - cur[0]);
  }, 0);
}

다시 한 번 제가 너무 형편없다고 느끼고 있습니다. 단순히 실력히 좋지 않다고 말하는 것보다, 어디서 이러한 차이가 오는 것인지 알고 싶습니다. 지금 저로써는 사람마다 특정 부분에 장단점이 있다고 밖에 생각해 낼 수가 없습니다. 그리고 제가 아는 저는 특출난 부분이 전혀 없습니다. 그래서 잘 할 수 있을 때까지 반복해서 연습을 하고, 익숙해지게 만드는게 저에게는 좋은 방법 같습니다. 그리고 시간을 낭비하지 않기 위해 최대한 효율적으로 배우고 실력이 늘 수 있도록, 잘 학습하는 방법에 대해서도 코딩을 배우며 틈틈히 고민해 나가야 한다고 생각합니다. 아무튼 사람들에게 도움을 줄 수 있는 괜찮은 프로그래머가 될 수 있었으면 좋겠습니다..ㅜㅜ

위 문제에서 배열 요소의 인데스 0은 항상 인덱스 1보다 작다는 조건이 있습니다. 제가 문제 풀이가 길고 복잡하고 어렵게 된 가장 큰 이유는 이 조건을 그냥 지나치고 처음 인자로 주어진 배열을 그대로 사용했기 때문입니다. 이 조건을 유의하고, 배열 요소의 인덱스 0을 기준으로 정렬을 한 배열을 기준으로 문제 풀이를 했으면 이렇게 어렵게 풀지는 않았을 거라 생각합니다. 인자로 주어진 배열을 정렬해서는 아래와 같이 풀 수 있었습니다.

function sumIntervals(intervals) {
  const sortedArr = intervals.sort((a, b) => a[0] - b[0]);
  let sum = 0;

  sortedArr.forEach((arr, idx) => {
    if (idx !== sortedArr.length - 1) {
      if (arr[1] < sortedArr[idx + 1][0]) {
        sum += arr[1] - arr[0];
      } else if (arr[1] >= sortedArr[idx + 1][0] && arr[1] <= sortedArr[idx + 1][1]) {
        sortedArr[idx + 1][0] = arr[0];
      } else if (arr[1] > sortedArr[idx + 1][1]) {
        sortedArr[idx + 1] = arr;
      }
    } else {
      sum += arr[1] - arr[0];
    }
  });

  return sum;
}

sort 메소드를 생략하면, 시간복잡도 O(n)으로 풀이되었습니다.

별도의 배열을 생성해서도 풀이를 해보고 싶어졌습니다. 아래 풀이는 친구의 풀이를 참고했는데, 저는 제목이 sum이라 무조건 숫자 사이의 간격을 합할 생각만 했는데, 아래의 풀이는 배열의 길이로 결과값을 반환했습니다. 저는 절대 생각 못 했을 문제 풀이라 생각하니 슬프네요. 하지만, 지금은 아래의 풀이를 이해를 했기 때문에 시간이 흘러도 생각을 해 낼 수 있을것 같습니다.

function sumIntervals(intervals) {
  const newArr = [];

  intervals.forEach(arr => {
    for (let i = arr[0]; i < arr[1]; i++) {
      if (!newArr.includes(i)) {
        newArr.push(i);
      }
    }
  });

  return newArr.length;
}

아래 풀이는 Best practice로 추천을 많이 받은 풀이입니다. 별도의 새로운 배열은 생성하지 않고 reduce를 활용했는데, 아래의 풀이를 보며 이렇게도 풀 수 있구나 하고 놀랐습니다..흑흑

function sumIntervals(intervals) {
  return intervals
    .sort((a, b) => a[0] - b[0])
    .reduce(
      (acc, array) => {
        if (array[1] > acc.top) {
          acc.total += array[1] - Math.max(acc.top, arr[0]);
        }

        array.top = Math.max(acc.top, arr[1]);
        return acc;
      },
      { total: 0, top: 0 }
    );
}

Handmade with .