[CS/알고리즘] 라인 스위핑 알고리즘

황제연·2025년 3월 27일

라인 스위핑 알고리즘

CS학습

목록 보기

26/193

🔍 라인 스위핑 (Line Sweeping)

라인 스위핑은 말 그대로 선을 쓸면서 문제를 해결하는 알고리즘입니다.
조금 더 쉽게 비유하자면, 막대기를 잡고 직선의 왼쪽 끝에서 오른쪽 끝까지 천천히 이동하면서
발생하는 이벤트들을 하나씩 처리하는 방식입니다

주로 1차원 구간에서 이벤트나 조건이 겹치는지,
또는 특정 구간에 몇 개의 이벤트가 존재하는지 등을 파악할 때 사용합니다

📌 라인 스위핑 동작방식

라인 스위핑의 동작 방식은 크게 3단계로 나눌 수 있습니다

이벤트 정리하기
먼저 처리할 모든 이벤트를 정리해 자료구조에 담습니다
예를 들어, 구간의 시작점과 끝점이 이벤트가 될 수 있습니다
이벤트 정렬하기
이벤트를 좌표 기준으로 정렬합니다
좌표가 같을 경우, 문제 조건에 따라 추가적인 우선순위로 정렬합니다
스위핑 시작하기
왼쪽부터 오른쪽으로 이동하면서 각 이벤트를 하나씩 처리합니다

📌 장점

빠른 속도
이벤트를 미리 정렬하고 관리하면 시간복잡도를 브루트포스보다 개선할 수 있습니다

🚀 라인 스위핑이 적용된 문제

LeetCode의 2025-03-26 데일리 문제는 라인 스위핑으로 해결할 수 있습니다

이 문제는 특정 기간 days 동안 진행되는 여러 회의들의 시작 시간과 종료 시간이 주어지고,
전체 일정 중, 회의가 열리지 않은 총 기간을 구하는 문제입니다

브루트 포스로 모든 날짜를 체크할 수 있지만 배열 크기와 날짜 범위때문에 시간 초과가 발생합니다
이때 라인 스위핑을 적용하면 문제를 해결할 수 있습니다

회의의 모든 일정을 일자별로 업데이트하면 시간초과가 발생합니다
이를 해결하기 위해 차분배열을 TreeMap에 적용하는 방식으로 고안했습니다

TreeMap을 사용하여 날짜를 키(key)로 하고, 해당 날짜의 회의 개수를 값(value)으로 설정하여 관리합니다
회의의 시작 날짜는 회의 개수를 +1, 종료 날짜 다음 날에는 회의 개수를 -1로 업데이트합니다
TreeMap에 의해 일자를 기준으로 오름차순 정렬됩니다

TreeMap<Integer, Integer> map = new TreeMap<>();
int ans = 0; // 휴일
int prev = days; // 이전 날짜
int count = 0; // 현재 회의 수
for(int[] meeting : meetings){
	prev = Math.min(prev, meeting[0]);
	map.put(meeting[0], map.getOrDefault(meeting[0], 0) + 1);
	map.put(meeting[1]+1, map.getOrDefault(meeting[1]+1, 0) - 1);
}

이렇게 하면 라인 스위핑의 첫 번째와 두 번째 단계가 완료됩니다
이제 세 번째 단계인 실제 스위핑 작업을 시작합니다

먼저, 첫 번째 회의 시작 전까지의 날짜를 휴일에 추가합니다

그 다음엔 날짜를 순서대로 확인하면서 현재 진행 중인 회의가 없다면 그 기간을 휴일에 더합니다

마지막으로 마지막 회의 종료 후 일정의 끝까지의 남은 일자를 휴일에 추가합니다

ans += (prev - 1);
for(Map.Entry<Integer, Integer> entry : map.entrySet()){
	int cur = entry.getKey();
	if(count == 0){
		ans += (cur - prev);
	}
	count += entry.getValue();
	prev = cur;
}
ans += days - prev + 1;

이렇게 하면 라인 스위핑을 통해 최종 결과를 효율적으로 얻을 수 있습니다