겹치는 선분의 길이

문제

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

선분이 두 개 이상 겹친 곳은 [-2, -1], [0, 1]로 길이 2만큼 겹쳐있습니다.

접근방법

이 문제의 핵심은 각 선분의 시작점과 끝점을 활용하여 겹치는 구간을 찾는 것이다. 그래서 이를 위해서는 각 선분의 시작점과 끝점을 나열하고, 선분의 시작점을 만날 때마다 겹치는 선분의 수를 증가시키고, 선분의 끝점을 만날 때마다 겹치는 선분의 수를 감소시키면 된다.

1. 각 선분의 시작점과 끝점을 나열하고 정렬.
2. 선분의 시작점과 끝점을 구분하기 위해 각 점에 레이블을 부여.

• 선분의 시작점과 끝점을 시간 순서대로 방문하면서 겹치는 선분의 수를 계산가능.

3. 선분의 시작점을 방문할 때마다 겹치는 선분의 수를 증가시키고, 선분의 끝점을 방문할 때마다 겹치는 선분의 수를 감소.

• 어느 시점에 겹치는 선분의 수가 두 개 이상이 되는 지점을 찾을 수 있음

4. 겹치는 선분의 수가 두 개 이상인 구간의 길이를 합산하여 반환.

• 이 구간의 길이는 현재 점의 위치와 이전 점의 위치의 차이로 계산가능.

풀이

function solution(lines) {
    const points = [];
    for (let line of lines) {
        points.push([line[0], 1]);
        points.push([line[1], -1]); 
    }
    points.sort((a, b) => a[0] - b[0] || b[1] - a[1]);

    let overlap = 0;
    let last = 0;
    let result = 0;

    for (let point of points) {
        if (overlap >= 2) {
            result += point[0] - last;
        }
        overlap += point[1];
        last = point[0];
    }

    return result;
}

핵심과 접근 방법이 어렵다. 그래도 이를 잘 풀어서 코드화 하면 위와 같은데, 정리해보자.

먼저 각 선분의 시작점과 끝점을 points 배열에 추가합니다. 이때, 선분의 시작점에는 1을, 끝점에는 -1을 부여하여 두 점을 구분한다. 그 다음 points 배열을 정렬하여 선분의 시작점과 끝점을 시간 순서대로 방문할 수 있도록 해야 한다. 이때, 시작점과 끝점이 같은 위치에 있는 경우, 먼저 끝점을 방문하도록 정렬 조건에 끝점을 우선시하는 조건을 추가하면 된다.

변수는 다음과 같은데,

1. overlap : 겹치는 선분의 수
2. last : 마지막으로 방문한 점
3. result : 겹치는 구간의 길이

이를 놓고 보면, points 배열을 순회하면서 겹치는 선분의 수를 계산하고, 겹치는 구간의 길이를 합산한다. 이때, 겹치는 선분의 수가 두 개 이상이면 현재 점의 위치와 이전 점의 위치의 차이를 결과에 더한다.

마지막으로, 겹치는 선분의 수와 마지막으로 방문한 점의 위치를 갱신하고, 이 과정을 points 배열의 모든 점에 대해 반복한 다음 반환한다.

정리하기

매우 어려운 문제다. 그렇기 때문에 많은 걸 요구하는데, 해결 능력, 구현 능력, 그리고 이해력이 요구되는 문제였다. 그래서 복잡도를 이해하고, 최적의 알고리즘을 선택하는 능력이 중요했던 거 같다.