다음과 같은 입력 배열과 출력 배열이 있다고 가정해 보겠습니다.
const input = ["0:3", "1:3", "4:5", "5:6", "6:8"];
const output = [
[0, 1, 3],
[4, 5, 6, 8]
];
각 숫자를 그래프의 노드(node)로, 각 쌍 x:y를 노드 x와 y를 잇는 간선(edge)으로 생각해 봅시다. 우리가 해야 할 과제는 정의된 간선을 통해 서로 이동할 수 있는 숫자들의 집합을 찾는 것입니다.
그래프 이론 관점에서 표현하면, 이는 그래프 안에서 서로 다른 연결 요소(connected components)를 찾는 문제와 같습니다. 예를 들어 위 배열에서는 4에서 0으로 이동할 수 있는 경로가 없기 때문에 두 숫자는 서로 다른 그룹에 속합니다. 반면 1은 3을 거쳐 0에 도달할 수 있으므로 같은 그룹으로 묶입니다.
다시 말해, 원하는 출력은 임의의 입력 집합을 바탕으로 서로 이동 가능한 노드들을 하나의 그룹으로 묶은 결과입니다. 따라서 주어진 입력으로부터 원하는 출력을 만들어 내는 JavaScript 함수를 작성해야 합니다.
알고리즘 접근 방식
이 문제는 다음 단계로 해결할 수 있습니다.
1. 각 쌍을 ':' 기준으로 분리한 뒤, 쌍 내부에서 숫자 크기순으로 정렬합니다.
2. 첫 번째 값을 기준으로 전체 쌍을 오름차순 정렬합니다.
3. 배열을 순회하면서 현재 쌍의 시작 값이 마지막 그룹의 최대값보다 크면 새로운 그룹을 생성하고, 그렇지 않으면 기존 그룹에 병합합니다.
4. 최종적으로 각 그룹에서 중복을 제거하고 오름차순으로 정렬하여 반환합니다.
예시
const input = ["0:3", "1:3", "4:5", "5:6", "6:8"];
const groupRange = (arr = []) => {
const res = [[]];
let count = 0;
const a = [0];
let array = arr
.map(el => el.split(':').sort((a, b) => a - b))
.sort((a, b) => a[0] - b[0]);
array.forEach(el => {
if (el[0] > a[a.length - 1]) {
res.push(el);
a.push(el[1]);
count++;
} else {
res[count] = res[count].concat(el);
a[a.length - 1] = el[1];
}
});
return res.map(el => [...new Set(el)].sort((a, b) => a - b));
}
console.log(groupRange(input));
코드 설명
split(':')은 문자열 쌍을 두 개의 값으로 나누고, sort()를 통해 각 쌍과 전체 배열을 정렬합니다. 순회 중에는 현재 쌍의 시작 값이 이전 그룹의 끝값보다 큰지 비교하여 새 그룹을 만들지 기존 그룹에 합칠지 결정합니다. 마지막에는 Set 객체를 활용해 중복 값을 제거한 뒤 정렬된 결과를 반환합니다.
출력
콘솔에 표시되는 결과는 다음과 같습니다.
[ [ '0', '1', '3' ], [ '4', '5', '6', '8' ] ]
참고로 split() 메서드는 문자열을 반환하기 때문에 결과 배열의 요소들이 문자열 형태로 출력됩니다. 필요하다면 Number() 또는 parseInt()를 사용해 숫자형으로 변환할 수 있습니다.