[알고리즘] LeetCode 57. Insert Interval JS

개요

2차원 배열 intervals와 1차원 배열 newInterval이 들어온다. intervals 배열은 시작 시간과 끝나는 시간을 나타내는 정수 1차원 배열을 원소로 갖는다

 

이때 1차원 배열 newInterval을 intervals 배열에 넣으려고 할때 시간이 겹쳐지지 않도록 겹쳐지는 부분을 합병해서 변경된 intervals 배열을 리턴하는게 문제이다.

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

시간으로 생각하면 이해하기 쉽다. 1시~3시까진데 중간에 2~5시 인터벌이 들어와 1시~5까지가 되었다.

Insert Interval - LeetCode

 

풀이

단순한 배열로 구현하는 문제라 처음 문제를 읽고 코드를 짜서 테스트 케이스는 금방 통과하게 되었다. 그런데 실제 제출을 했을 때 걸리는 부분이 많았고 걸리는 부분을 계속 if를 추가하고 한줄한줄씩 더하다보니 너무 스파게티가 되는거 같아 갈아엎게 되었다. 이후 계속 고민하다가 집중이 안되기 시작할 때 다른 사람의 코드를 참고하여 해결했다.

 

내 코드의 문제가 있었던 부분은 조건이었다. 케이스를 나누는 조건에서 나눠질 수 있는 경우만 생각하다보니 점점 더 길어졌고 수정하기 어려워졌다. 이때 다른 코드를 참고했을 때 굳이 참이되는 케이스로만 구성하는게 아니라 거짓이 되는 경우로도 만들 수 있다는 부분이었다. 이 부분을 놓쳐서 계속 한가지만 붙잡고 있었던거 같다.

var insert = function (intervals, newInterval) {
  let [nStart, nEnd] = newInterval;
  const len = intervals.length;
  if (len && nEnd < intervals[0][0]) return [newInterval, ...intervals];
  const answer = [];
  let i = 0;

  //시작 위치 찾기
  for (; i < len; i++) {
    if (
      (intervals[i][0] <= nStart && nStart <= intervals[i][1]) ||
      (intervals[i][0] <= nEnd && nEnd <= intervals[i][1])
    ) {
      nStart = nStart < intervals[i][0] ? nStart : intervals[i][0];
      answer.push([nStart, 0]);
      nEnd = nEnd < intervals[i][1] ? intervals[i][1] : nEnd;
      break;
    } else answer.push(intervals[i]);
  }

  //시작위치가 없다면
  if (i === len) return [...answer, newInterval]; //전부 탐색했는데 없는 경우는 맨 뒤에 붙는다.

  //끝나는 위치 찾기
  for (; i < len; i++) {
    if (intervals[i][1] > nEnd) {
      if (intervals[i][0] <= nEnd) {
        nEnd = intervals[i][1];
        continue;
      } else break;
    }
  }

  //남은 배열 자르기
  answer[answer.length - 1][1] = nEnd;
  answer.push(...intervals.slice(i));

  return answer;
};

 

 

/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 *
 * intervals 배열엔 start, end가 들어있다
 * 이때 newInterval로 새로운 start와 end가 들어오는데 시간이 오버랩되는 부분을 묶어라
 * 처음 위치는 시작과 newInterval로 찾으면 된다.
 */
var insert = function (intervals, newInterval) {
  if (!intervals.length) return [...newInterval];
  let i = 0;
  let [nStart, nEnd] = newInterval;
  const answer = [];

  for (; i < intervals.length; i++) {
    const interval = intervals[i];
    // 수정이 시작되는 조건은 기존의 인터벌 시작시간이 새로 들어오는 인터벌의 사이에 있을 떄 발생한다.
    // 따라서 인터벌 전에 있는 조건들은 새로 들어오는 것과는 관련이 없다.
    if (interval[1] < nStart) answer.push(interval);
    else if (nEnd < interval[0]) break;
    else {
      nStart = Math.min(nStart, interval[0]);
      nEnd = Math.max(nEnd, interval[1]);
    }
  }

  answer.push(...intervals.slice(i));

  return answer;
};

회고

최근 알고리즘 문제를 계속 풀고 어려운 문제를 만나면서 잘 안풀리면 정답을 보는 것이 너무 쉽게 푸는거 아닐까하는 고민이 생기게 되었다. 내 입장에서는 도저히 안풀리는 것처럼 느껴지긴하는데 막상 풀어낸 코드를 보면 허무하다고 느껴진다. 이럴때보면 기본기가 부족한가 싶어 다시 기초 수준 문제로 돌아가게 되고 이런 부분들이 스스로에게 스트레스가 되고 부족함만 느껴 발전이 없다고 스스로 생각하게 된다..

 

그래서 최대한 문제를 적게 풀더라도 혼자 푸는 시간을 기존에 제안된 시간보다 최소 2배는 늘려보려고 한다. 대략 한시간이지만 그래도 이정도는 고민해봐야할 거 같다.

 

앞으로 4학년 2학기로 졸업과 취업이 가까워지면서 조급한 마음이 드는 것이라 생각되서 안좋은 방식으로 푸는게 아닐까 생각됐다. 하지만 여러 글을 참고해봤을 때 나만의 기준이 필요하다고 생각했고 그 기준이 현재의 나한테는 1시간이라고 생각했다. 조금 더 여유를 가지고 생산성을 높여보자고 회고글을 작성했다 ㅎㅎ