어떻게 Line Sweep Algorithm을 알게 되었는가?
현재 알고리즘 스터디에서 매주 LeetCode의 Weekly Contest 문제를 풀고 있습니다. 이번 주에는 Weekly Contest 400에 출제된 "Count Days Without Meetings" 문제를 풀면서 Line Sweep Algorithm을 알게 되었습니다. 문제를 해결하기 위해 Discuss 탭에서 힌트를 얻었고, 그 과정에서 이 알고리즘을 접하게 되었습니다.
Line Sweep Algorithm이란?
Line Sweep Algorithm은 "선 스위핑 알고리즘"으로 번역되며, 주로 좌표 평면 상의 여러 선이나 구간이 겹치는 문제를 해결하는 데 사용됩니다. 이 알고리즘은 하나의 수직선(선 스위프)를 가로질러 이벤트들을 처리하면서 문제를 해결하는 방식으로 동작합니다.
Count Days Without Meetings 문제
직원이 근무할 수 있는 총 일수(1일부터 시작)를 나타내는 양의 정수 일수가 제공됩니다. 또한 크기 n의 2D 배열 회의가 제공됩니다. 여기서 회의[i] = [start_i, end_i]는 회의 i(포함)의 시작 및 종료 날짜를 나타냅니다.
직원이 근무할 수 있지만 예정된 회의가 없는 일수를 반환합니다.
참고: 회의가 겹칠 수 있습니다.
Example:
Input: days = 5, meetings = [[2, 4], [1, 3]]
Output: 1
Explanation: There is no meeting scheduled on the 5th day.
Count Days Without Meetings 문제가 Line Sweep Algorithm을 활용해야 하는 이유?
문제는 주어진 총 일수와 각 회의의 시작 및 종료 날짜가 주어졌을 때, 회의가 없는 날의 수를 계산하는 문제입니다. 문제 설명에서 회의가 겹칠 수 있습니다. 라는 문장을 통해 구간이 겹치는 부분이 있다는 것을 알 수 있습니다. Line Sweep Algorithm은 구간이 겹치는 문제를 해결하는 데 효과적이므로, 이 문제에 적합하다고 생각합니다.
Line Sweep Algorithm 활용하여 문제 풀기
Line Sweep Algorithm은 시간 또는 공간을 따라가면서 이벤트를 처리하는 방식입니다. 이 문제에서는 날짜를 따라가면서 각 날짜에 회의가 있는지 확인하는 방식으로 문제를 해결합니다.
문제 해결 방법
- 이벤트 생성: 회의의 시작과 끝을 이벤트로 변환합니다.
- [예][2,4] 회의는 (2, "start")와 (4 + 1, "end") 이벤트로 변환합니다.
- 종료일 다음 날을 표시하는 이유? 같은 날 종료된 회의와 시작된 회의를 구분하기 위해서입니다.
- [예][2,4] 회의는 (2, "start")와 (4 + 1, "end") 이벤트로 변환합니다.
- 이벤트 정렬: 모든 이벤트를 시간 순서대로 정렬합니다.
- 정렬하면 시간이 흐름에 따라 회의가 시작되고 끝나는 것을 알 수 있습니다.
- 이벤트 처리: 현재 날짜에서 진행 중인 회의 수를 추적합니다.
- 회의가 시작되면 진행 중인 회의 수를 증가시킵니다.
- 회의가 끝나면 진행 중인 회의 수를 감소시킵니다.
- 진행 중인 회의가 0인 날짜를 찾아 회의가 없는 날로 기록합니다.
Example 설명
- 입력
- days: 5일
- meetings: [[2, 4], [1, 3]]
- 출력
- 회의가 없는 날의 수: 1일(5일)
- 단계별 설명
- 이벤트 생성
- [2, 4] 회의는 (2, "start")와 (4 + 1, "end")로 변환
- [1, 3] 회의는 (1, "start")와 (3 + 1, "end")로 변환
- 이벤트 정렬
- 이벤트를 시간 순으로 정렬 후: [(1, "start"), (2, "start"), (3 + 1, "end"), (4 + 1, "end")] 가 됩니다.
- 이벤트 처리
- 변수 초기화
-availableDays: 회의가 없는 날의 수를 저장할 변수
-currMeetings: 현재 진행 중인 회의 수를 추적할 변수
-prevDay: 마지막으로 처리한 날짜를 추적할 변수- 이벤트를 순회하면서 각 이벤트를 처리합니다.
- 날짜 사이에 회의가 없는 날을 계산합니다.
- 모든 이벤트를 처리한 후, 마지막 이벤트 날짜 이후부터 주어진 총 일수까지 회의가 없는 날을 계산합니다.
- 변수 초기화
- 이벤트 생성
구현 코드
var countDays = function (days, meetings) {
const START = "start";
const END = "end";
// 이벤트를 저장할 배열 생성
const events = [];
// meetings 배열의 각 요소를 순회하며 이벤트 생성
for (const [s, e] of meetings) {
events.push([s, START]); // 시작일 이벤트 추가
events.push([e + 1, END]); // e + 1의 의미? 끝난 다음 날을 나타냄. 종료일 이벤트 추가
}
// events 배열 정렬
// [day, event type]
events.sort((a, b) => {
// 날짜가 다른 경우, 날짜 기준으로 정렬
if (a[0] !== b[0]) {
return a[0] - b[0];
}
// 날짜가 같은 경우, 이벤트 타입이 "start"가 "end"보다 앞에 오도록 정렬
else {
// a는 start type, b는 end type 일 경우 a가 먼저 오도록 음수 반환
if (a[1] === START && b[1] === END) {
return -1;
}
// a가 end type, b가 start type일 경우 b가 먼저 오도록 양수 반환
else if (a[1] === END && b[1] === START) {
return 1;
}
// 둘 다 같은 타입인 경우, 순서 변경 없음
else {
return 0;
}
}
});
// 회의가 없는 날을 저장할 변수 availableDays 선언 및 초기화
let availableDays = 0;
// 현재 진행 중인 meeting 수를 저장할 변수 currMeetings 선언 및 초기화
let currMeetings = 0;
// 현재 이벤트를 처리하기 전에 마지막으로 처리한 날짜를 저장하는 변수 prevDay 선언 및 초기화
let prevDay = 1;
// events 배열 순회
for (const [day, type] of events) {
// 이벤트를 마지막으로 처리한 날과 현재 이벤트의 날 사이에 회의가 없는 날을 계산
if (prevDay < day) {
// 현재 진행되는 회의가 없는 경우 availableDays에 비어있는 날 추가
if (currMeetings === 0) availableDays += day - prevDay;
// prevDay를 현재 이벤트의 날로 업데이트
prevDay = day;
}
// type이 start 인 경우 현재 진행중인 회의 증가
if (type === START) currMeetings++;
// type이 end 인 경우 현재 진행중인 회의 감소
else currMeetings--;
}
// 모든 이벤트가 처리된 후, 마지막 이벤트 날짜 이후부터 주어진 총 일수까지 회의가 없는 날을 계산
if (prevDay <= days && currMeetings === 0)
availableDays += days - prevDay + 1;
// 회의가 없는 비어있는 날 반환
return availableDays;
};코드의 시간복잡도
- 이벤트 생성: O(n)
- 이벤트 정렬: O(nlogn)
- 이벤트 처리: O(n)
총 시간복잡도: O(nlogn)
결론(알게된 것)
- Line Sweep Algorithm은 하나의 수직선(선 스위프)를 가로질러 이벤트들을 처리하면서 문제를 해결하는 알고리즘 기법입니다.
- Line Sweep Algorithm은 구간이 겹치는 부분을 해결하는 데 유용합니다.
참고 자료
