Skip to content

Latest commit

 

History

History
97 lines (79 loc) · 5.54 KB

겹치는_선분의_길이.md

File metadata and controls

97 lines (79 loc) · 5.54 KB

겹치는 선분의 길이

프로그래머스

문제

선분 3개가 평행하게 놓여 있습니다. 세 선분의 시작과 끝 좌표가 [[start, end], [start, end], [start, end]] 형태로 들어있는 2차원 배열 lines가 매개변수로 주어질 때, 두 개 이상의 선분이 겹치는 부분의 길이를 return 하도록 solution 함수를 완성해보세요.

제한사항

  • lines의 길이 = 3
  • lines의 원소의 길이 = 2
  • 모든 선분은 길이가 1 이상입니다.
  • lines의 원소는 [a, b] 형태이며, a, b는 각각 선분의 양 끝점 입니다.
    • -100 ≤ a < b ≤ 100

제출 코드

function solution(lines) {
  function getOverlapLine(line1, line2) {
    if (line1[1] <= line2[0] || line1[0] >= line2[1]) return null;
    if (line1[0] >= line2[0] && line1[1] <= line2[1]) return line1;
    if (line2[0] >= line1[0] && line2[1] <= line1[1]) return line2;
    if (line1[0] <= line2[0]) return [line2[0], line1[1]];
    return [line1[0], line2[1]];
  }

  function splitLine(line) {
    if (!line) return [];
    const splittedLines = [];
    for (let i = line[0]; i < line[1]; i++) {
      splittedLines.push(`${i}${i + 1}`);
    }
    return splittedLines;
  }

  const overlapAB = getOverlapLine(lines[0], lines[1]);
  const overlapBC = getOverlapLine(lines[1], lines[2]);
  const overlapAC = getOverlapLine(lines[0], lines[2]);
  const splittedOverlapAB = splitLine(overlapAB);
  const splittedOverlapBC = splitLine(overlapBC);
  const splittedOverlapAC = splitLine(overlapAC);
  return new Set([
    ...splittedOverlapAB,
    ...splittedOverlapBC,
    ...splittedOverlapAC,
  ]).size;
}

풀이 과정

첫 번째 풀이

  • 처음에는 합집합과 교집합의 개념으로 접근하려 했다.
    1. 세 선분 A, B, C를 선분이 포함하는 점의 배열로 변환한다(예) [1, 3] -> [1, 2, 3]).
    2. AB, BC, AC 짝으로 각각 점의 교집합을 구한다(예) A가 [1, 2, 3]이고 B가 [2, 3, 4]일 때 둘의 교집합은 [2, 3]이다.).
    3. AB, BC, AC의 교집합들의 합집합을 구한다.
    4. 합집합에 들어있는 점의 개수를 최종적으로 반환한다.
  • 문제는 점의 집합만을 가지고서는 선분을 어떻게 연결해야 하는지 알 수 없다는 점이다.
  • 예를 들어 [1, 2, 3, 4]라는 합집합이 구해졌다면 이것이 12, 34 선분을 의미하는 것인지(길이 2), 1~4 선분을 의미하는 것인지(길이 3) 알 수 없다.
  • 또한, 1번 과정에서 세 선분을 점의 배열로 변환하는 과정에서 선분의 길이가 길어질수록 시간복잡도가 같이 증가하게 된다.

두 번째 풀이

  • 첫 번째 풀이의 첫 번째 문제점은 세 선분의 길이가 증가할 때 시간복잡도도 같이 증가한다는 것이다.
    • 하지만 선분의 길이와는 관계 없이 정해진 수의 조건문으로 두 선분이 겹치는지를 알 수 있으므로 위의 방법은 성능 낭비이다.
    • 먼저, 두 선분이 안 겹치는 경우는 다음과 같다.
      1. 첫 번째 선분의 y값이 두 번째 선분의 x값과 같거나 작을 경우.
      2. 두 번째 선분의 x값이 첫 번째 선분의 y값과 같거나 클 경우.
    • 두 선분이 겹치는 경우는 다음과 같다.
      1. 첫 번째 선분이 두 번째 선분 안에 포함되는 경우.
      2. 첫 번째 선분이 두 번째 선분을 포함하는 경우.
      3. 첫 번째 선분이 두 번째 선분의 왼쪽에 걸쳐 있는 경우.
      4. 첫 번째 선분이 두 번째 선분의 오른쪽에 걸쳐 있는 경우.
    • 위의 조건을 거쳐 겹치는 선분의 끝 점을 [x1, x2] 형태로 구한다.
  • 첫 번째 풀이의 두 번째 문제점은 점의 집합으로 선분이 어떻게 그려지는지를 알 수 없다는 것이다.
    • 앞서서 AB, BC, AC 선분의 겹치는 구간을 [x1, x2] 형태로 구했다.
    • 이 선분을 각각 길이 1단위로 나눠 배열 안에 담는다.
    • 예를 들어, 겹치는 구간이 [3, 5]라면 [[3, 4], [4, 5]]로 변환한다.
    • 이후 변환된 AB, BC, AC 배열의 합집합을 구한 후 요소의 갯수를 반환하면 정답이 된다.
  • 두 번째 풀이의 문제점은 마지막 처리인 합집합을 구하는 과정에 있었다.
    • 세 배열의 중복을 제거하기 위해 세 배열을 한 배열 안에 풀고, Set 객체를 사용했다.
    • 하지만 객체 타입인 배열은 배열 안에 들어있는 요소가 동일하더라도 같은 인스턴스가 아닌 이상 같은 값이 아니다.
    • 따라서 Set 객체를 사용해도 중복된 요소가 제거되지 않았다.

마지막 풀이

  • 두 번째 풀이와 기본적인 논리는 동일하나, 마지막에 Set 집합으로 중복을 제거할 수 있도록 하기 위해 코드를 일부 수정했다.
    • 두 번째 풀이에서는 겹치는 구간을 1단위로 나눠 담은 배열을 [[1, 2], [2, 3]]과 같은 형태로 저장했다.
    • 이 부분을 ["1-2", "2-3"]과 같은 형태로 수정했다.
    • 배열의 각 요소가 객체 타입이 아니라 문자열 타입이 되면서 Set 객체로 중복 요소를 제거할 수 있게 되었다.

알고 가자

  • 자바스크립트에서 객체 타입이 서로 같다고 평가되는 경우는 오직 같은 인스턴스인 경우 뿐이다. 동일한 속성-값 쌍을 지닌 객체를 같은 객체로 판단하고 싶다면 속성 하나하나를 비교하여 일치 여부를 판별하는 함수를 직접 만들거나 외부 라이브러리를 사용해야 한다.