JavaScript로 가장 긴 페어 체인(연쇄)의 길이 찾기

문제 설명

숫자 쌍(pair)으로 이루어진 배열 arr을 첫 번째 인자로 받는 JavaScript 함수를 작성해야 합니다. 각 쌍에서 항상 첫 번째 숫자가 두 번째 숫자보다 작다는 조건이 주어집니다.

여기서 한 쌍 (c, d)는 다른 쌍 (a, b)을 따라올 수 있다고 정의합니다. 이때 조건은 b < c, 즉 앞선 쌍의 두 번째 숫자가 뒤따르는 쌍의 첫 번째 숫자보다 작아야 한다는 것입니다. 이러한 방식으로 여러 쌍을 연결하여 '체인(chain)'을 만들 수 있으며, 우리 함수는 이렇게 형성할 수 있는 가장 긴 체인의 길이를 반환해야 합니다.

입력 예시

const arr = [
    [1, 2], [2, 3], [3, 4]
];

출력 예시

const output = 2;

출력 설명

가장 긴 체인은 [1,2] → [3,4]입니다. [2,3]은 [1,2]와 연결될 수 없는데, [1,2]의 두 번째 숫자 2가 [2,3]의 첫 번째 숫자 2보다 작지 않기 때문입니다(b < c 조건 실패). 따라서 최대 체인 길이는 2가 됩니다.

접근 방법: 그리디 알고리즘

이 문제는 그리디(Greedy) 전략으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1. 모든 쌍을 두 번째 숫자(끝 값)를 기준으로 오름차순 정렬합니다.
2. 정렬된 순서대로 배열을 순회하면서, 현재 쌍의 시작 값이 이전에 선택한 쌍의 끝 값보다 크면 체인에 추가합니다.
3. 끝 값이 작은 쌍부터 선택하면 이후에 더 많은 쌍을 연결할 여지가 생기므로, 이 전략이 항상 최적의 결과를 보장합니다.

시간 복잡도는 정렬로 인해 O(n log n)이며, 공간 복잡도는 O(1)입니다.

구현 코드

const arr = [
[1, 2], [2, 3], [3, 4]
];
const findLongestChain = (arr = []) => {
    // 끝 값을 기준으로 오름차순 정렬
    arr.sort(([, b], [, d]) => b - d)
    let currentEnd = arr[0][1]
    let count = 1
    for (const [start, end] of arr) {
        // 현재 쌍의 시작 값이 이전 끝 값보다 크면 체인에 추가
        if (start > currentEnd) {
            count += 1
            currentEnd = end
        }
    }
    return count
}
console.log(findLongestChain(arr));

실행 결과

2

코드 동작 원리 상세 분석

위 코드를 단계별로 살펴보겠습니다.

1단계 — 정렬: arr.sort(([, b], [, d]) => b - d)는 구조 분해 할당을 활용해 각 쌍의 두 번째 요소를 추출하여 비교합니다. 정렬 결과는 [[1,2], [2,3], [3,4]]입니다.

2단계 — 초기화: currentEnd를 첫 번째 쌍의 끝 값인 2로 설정하고, count는 1로 초기화합니다(첫 번째 쌍은 이미 체인에 포함).

3단계 — 순회: 각 쌍을 확인하며 start > currentEnd 조건을 만족하면 count를 증가시키고 currentEnd를 갱신합니다. [2,3]의 경우 start가 2이고 currentEnd가 2이므로 조건을 만족하지 않아 건너뛰고, [3,4]의 경우 start가 3 > 2이므로 count가 2가 됩니다.

최종적으로 가장 긴 체인의 길이인 2가 출력됩니다.