스윕 라인 알고리즘 적용을 통한 로직 개선

DatePicker 라는 일정 조율 웹서비스를 개발하면서, 사용자들이 등록한 스케줄을 기반으로 가장 많은 인원이 동시에 가능한 시간대를 계산하는 기능을 구현하게 되었습니다. 이 과정에서 단순히 겹치는 시간대만 구하는 게 아니라, 해당 시간대에 참여 가능한 사용자 ID 목록도 함께 반환해야 했습니다.

🔍누적 배열을 통한 구현

가장 먼저 떠올린 방식은 누적 배열을 이용한 방법이었습니다.

• 분 단위로 시간 범위를 잘게 나눈 배열을 생성하고,
• 각 사용자의 가능한 시간 범위에 대해
  - 시작 시간에는 +1,
  - 종료 시간에는 -1 을 기록
• 마지막에 배열을 순회하며 누적합을 계산해 가장 큰 값이 나오는 시간대를 찾는 방식입니다.

// 예시 
int[] timeline = new int[24 * 60]; // 24시간 분 단위
timeline[startMinute] += 1;
timeline[endMinute] -= 1;

🤔 문제 발생

하지만 이 방식은 "언제 가장 많은 인원이 가능한가?" 라는 질문에는 잘 맞지만, "그 시간대에 가능한 사람은 누구인가?" 라는 요구사항에는 잘 맞지 않았습니다.

만약 해당 시간대에 가능한 사용자 리스트를 구하고자 한다면, 모든 시간 인덱스마다 userId 리스트를 따로 저장해야 하고, 이는 메모리 측면에서도 비효율적이며, 코드 또한 지저분해질 수밖에 없었습니다.

🔄 스윕 라인 (Sweep Line) 알고리즘 적용

이에 보다 효율적인 방식이 필요했고, 구글링을 통해 스윕 라인 알고리즘을 알게 되었습니다. 스윕 라인 알고리즘이란, 정렬된 요소들을 가장 빠른 요소부터 순회하며 답을 찾는 방식을 의미합니다.

각 사용자는 자신이 등록해 놓은 스케줄이 존재. 스케줄은 사용자가 해당 스케줄 시간에 자신이 이벤트 참여가 가능함을 의미한다.

적용 방식:

• 각 사용자 스케줄
  - 시작 시간에 userId 추가 (스케줄이 시작되었으므로 해당 시간대에 사용자 참여 가능)
  - 종료 시간에 userId 제거 (스케줄이 끝난다는 것은 더 이상 참여가 불가능함을 의미)
• 시간 순으로 자동 정렬되는 TreeMap<LocalDateTime, List<Long>> 를 활용해, 시간대 별로 정렬된 이벤트들을 관리
• 시간을 순서대로 순회하면서 현재 가능한 사용자 집합 (Set) 을 관리

// List<Long>: userId list
TreeMap<LocalDateTime, List<Long>> startMap = new TreeMap<>();
TreeMap<LocalDateTime, List<Long>> endMap = new TreeMap<>();

// TreeMap 에 시작 시간과 끝나는 시간을 각각 설정
// 해당 시간에 userId list 할당
for (ScheduleDto s : schedules) {
	startMap
			.computeIfAbsent(s.getStartTime(), t -> new ArrayList<>())
			.add(s.getUserId());
	endMap
			.computeIfAbsent(s.getEndTime(), t -> new ArrayList<>())
			.add(s.getUserId());
}

// times : 전체 시간 관리
List<LocalDateTime> times = new ArrayList<>();
times.addAll(startMap.keySet());
times.addAll(endMap.keySet());
Collections.sort(times); 

Set<Long> activeUsers = new HashSet<>(); // 해당 시간대에 참여 가능한 유저
int maxCount = 0; // 가장 많이 가능한 사용자 수

// 전체 시간을 순회하면서 가장 많이 가능한 인원 계산
for (LocalDateTime t : times) {

	// 스케줄이 끝나는 시간에는 TreeMap 에 설정된 userId 제거
	List<Long> ends = endMap.get(t);
	if (ends != null) ends.forEach(activeUsers::remove);

	// 스케줄이 시작되는 시간에는 TreeMap 에 설정된 userId 추가
	List<Long> starts = startMap.get(t);
	if (starts != null) activeUsers.addAll(starts);

	// 최대 참여 가능 인원 수 계산
	maxCount = Math.max(maxCount, activeUsers.size());
}

// 재순회를 위한 초기화
activeUsers.clear();
List<TimeSlotDto> slots = new ArrayList<>();

// 가장 많은 인원이 가능한 시간대 조회 및 반환
for (int i = 0; i < times.size() - 1; i++) {
	LocalDateTime t = times.get(i); 
	LocalDateTime nextT = times.get(i + 1);

	List<Long> ends = endMap.get(t);
	if (ends != null) ends.forEach(activeUsers::remove);

	List<Long> starts = startMap.get(t);
	if (starts != null) activeUsers.addAll(starts);

	// 현재 시간대에 활성화 된 사용자 수가 최대 참여 가능 수랑 같다면
	if (activeUsers.size() == maxCount) {
    	// 참여 가능한 userId list 생성
		List<Long> usersSnapshot = new ArrayList<>(activeUsers);
        // 가장 많은 인원이 가능한 시간대 반환
		slots.add(new TimeSlotDto(t, nextT, usersSnapshot));
	}
}

🫢 장점

• 특정 시간대에 참여 가능한 사용자 목록까지 실시간 추적 가능
• 누적 배열보다 메모리 효율성이 높고 가독성이 뛰어남
• O (N log N) 의 준수한 시간 복잡도 (정렬 및 순회)

마무리

이번 경험을 통해, 단순히 작동하는 코드보다 문제 요구사항에 정확히 부합하는 로직이 더 중요하다는 것을 다시 깨달았습니다. 또한, 익숙한 방식부터 시작하더라도, 필요하다면 상황에 따라 로직을 바꿀 수 있는 유연함도 필요하다는 점을 배울 수 있었습니다.

스윕 라인 알고리즘은 일정 관련 기능뿐 아니라, 다양한 구간 기반 문제에서도 자주 활용될 수 있으므로, 여러분들도 다양한 문제 상황에 적용할 수 있다면 좋겠습니다!