이 강좌는 자바스크립트 코딩 테스트에서 자주 출제되는 문제 중 하나인 “선분을 그룹으로 나누기”에 대해 다루고자 합니다.
본 문제는 주어진 선분들이 서로 겹치는 경우를 찾아서 이를 그룹으로 나누는 과정을 테스트합니다.
알고리즘 문제를 해결하는 과정에서 발생할 수 있는 다양한 상황과 고려해야 할 사항들을 상세히 살펴보겠습니다.
문제 정의
문제: 주어진 선분의 배열이 있을 때, 서로 겹치는 선분들을 그룹으로 묶어 그룹의 수를 반환하시오.
예를 들어, 다음과 같은 선분이 주어진다고 가정합시다:
선분: [[1, 3], [2, 4], [5, 6], [7, 10], [9, 11]]
이 배열에는 두 그룹이 존재합니다:
- 첫 번째 그룹: [[1, 3], [2, 4]]
- 두 번째 그룹: [[5, 6], [7, 10], [9, 11]]
문제 접근 방법
이 문제를 해결하기 위해 다음과 같은 접근 방식을 사용할 수 있습니다:
- 정렬: 선분의 시작점 또는 끝점을 기준으로 정렬합니다.
- 그룹화: 정렬된 선분을 순회하며 겹치는 선분들을 그룹으로 나눕니다.
1단계: 선분 정렬
선분을 시작점 기준으로 정렬합니다. 이렇게 하면 선분들이 겹치는 경우를 쉽게 판단할 수 있습니다.
2단계: 그룹화 로직 구현
정렬된 선분을 순회하면서 현재 선분이 이전 선분과 겹치는지를 확인합니다.
겹치지 않는 경우 새 그룹을 시작하고, 겹치는 경우 해당 그룹에 추가합니다.
예제 코드
위의 로직을 바탕으로 작성한 자바스크립트 코드는 다음과 같습니다.
function groupLines(lines) {
// 1. 선분을 시작점 기준으로 정렬
lines.sort((a, b) => a[0] - b[0]);
let groups = [];
let currentGroup = [];
for (let i = 0; i < lines.length; i++) {
const line = lines[i];
if (currentGroup.length === 0) {
currentGroup.push(line);
} else {
// 현재 선분의 시작점이 이전 선분의 끝점보다 작거나 같으면 겹친다.
if (line[0] <= currentGroup[currentGroup.length - 1][1]) {
currentGroup.push(line);
} else {
// 겹치지 않으면 그룹을 저장하고 새 그룹 시작
groups.push(currentGroup);
currentGroup = [line];
}
}
}
// 마지막 그룹을 추가
if (currentGroup.length > 0) {
groups.push(currentGroup);
}
return groups.length;
}
// 예제 입력
const lines = [[1, 3], [2, 4], [5, 6], [7, 10], [9, 11]];
console.log(groupLines(lines)); // 출력: 2
코드 설명
위 코드에서는 다음과 같은 과정을 통해 선분을 그룹으로 나누었습니다:
- 정렬: 선분 배열을 시작점 기준으로 오름차순으로 정렬하였습니다.
- 그룹 탐색: 각 선분을 순회하면서 현재 선분이 이전 선분과 겹치는지를 확인하였습니다.
- 그룹 저장: 겹치지 않는 선분을 만나면 현재 그룹을 저장하고 새 그룹을 시작합니다.
복잡도 분석
이 알고리즘의 시간 복잡도는 주로 정렬을 수행하는 부분에서 결정됩니다. 정렬은 O(n log n)이고, 선분을 순회하면서 그룹을 나누는 과정은 O(n)입니다.
따라서 전체 시간 복잡도는 O(n log n)입니다.
공간 복잡도는 최악의 경우 모든 선분이 겹치지 않을 때 O(n)입니다.
정리
이번 강좌에서는 “선분을 그룹으로 나누기”라는 문제를 통해 선분이 겹치는 경우를 판단하고 그룹화하는 방법을 알아보았습니다.
정렬과 탐색이라는 기본적인 알고리즘 기법을 이용하여 문제를 효과적으로 해결하는 과정을 살펴보았습니다.
이러한 알고리즘 문제는 실제 코딩 테스트에서 자주 출제되므로, 위와 같은 접근 방식을 연습하고, 다양한 변형 문제를 풀어보는 것이 중요합니다.
다음 강좌에서도 유용한 코딩 테스트 문제를 다룰 예정이니 많은 기대 바랍니다!