동시 재생자가 가장 많은 순간

자바스크립트 코딩테스트 문제로 sweep-line 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today medium sweep-line 함수명: solution 제한 시간: 300ms

각 사용자의 재생 구간이 [start, end]가 아니라 [start, end) 형태로 주어집니다. 즉 start 시각에는 재생 중이지만 end 시각에는 이미 재생이 끝난 상태입니다.

재생 로그 배열 logs가 주어질 때, 동시에 재생 중인 사용자가 가장 많았던 가장 이른 시각과 그때의 사용자 수를 [time, count] 형태로 반환하세요.

재생 로그가 비어 있으면 [-1, 0]을 반환합니다.

제한사항

0 <= logs.length <= 100,000
각 로그는 [start, end] 형태의 길이 2 배열입니다.
0 <= start < end <= 1,000,000,000
모든 시각은 정수입니다.
재생 구간은 start 이상 end 미만인 동안만 활성 상태입니다.
최대 동시 재생 수가 여러 시각에서 같다면 가장 이른 시각을 반환합니다.

예시

입력: [[1, 4], [2, 6], [4, 7], [5, 8]] → 출력: [5, 3]
입력: [[3, 5], [3, 7], [3, 4], [7, 9]] → 출력: [3, 3]
입력: [[1, 2], [2, 3], [3, 4]] → 출력: [1, 1]

세 번째 예시에서 [1, 2)와 [2, 3)은 시각 2를 동시에 포함하지 않습니다. 따라서 최대 동시 재생 수는 1이고, 그 값이 처음 만들어지는 가장 이른 시각은 1입니다.

힌트

각 로그를 그대로 비교하면 겹치는 모든 쌍을 확인해야 해서 비효율적일 수 있습니다.
시작 시각은 +1, 종료 시각은 -1 이벤트로 바꿔 생각해 보세요.
같은 시각에 종료와 시작이 함께 있다면, 이 문제에서는 종료를 먼저 처리해야 합니다.

해설

핵심은 모든 구간을 직접 겹쳐 보는 대신, 시간의 변화가 일어나는 지점만 추적하는 것입니다.

각 로그 [start, end)는 다음 두 이벤트로 바꿀 수 있습니다.

start 시각: 시청자 수 +1
end 시각: 시청자 수 -1

이 이벤트들을 모두 모아 시간순으로 정렬한 뒤 차례대로 처리하면, 각 시각에서 현재 재생 중인 사용자 수를 알 수 있습니다.

여기서 중요한 함정은 같은 시각에 종료 이벤트와 시작 이벤트가 함께 있을 때의 처리 순서입니다.

이 문제의 구간은 [start, end)이므로:

end 시각에는 이미 빠져 있어야 하고
start 시각에는 새로 들어와 있어야 합니다.

그래서 같은 시각이라면 종료(-1)를 먼저, 시작(+1)를 나중에 처리해야 실제 의미와 맞습니다.

예를 들어 [1, 2)와 [2, 3)은 겹치지 않으므로, 시각 2에서는 먼저 앞 구간이 빠지고 그 다음 뒤 구간이 들어와야 합니다.

풀이 흐름은 다음과 같습니다.

로그가 비어 있으면 [-1, 0]을 반환합니다.
각 로그를 시작 이벤트와 종료 이벤트 두 개로 변환합니다.
이벤트를 (시간 오름차순, 같은 시간이면 종료 먼저) 기준으로 정렬합니다.
이벤트를 순서대로 보며 현재 시청자 수를 갱신합니다.
지금까지 본 최대값보다 큰 값이 나오면 [현재 시각, 현재 수]로 정답을 갱신합니다.
최대값과 같은 경우는 더 이른 시각이 이미 먼저 등장했으므로 그대로 둡니다.

이 방법의 시간 복잡도는 이벤트 정렬 때문에 O(n log n)이고, 추가 공간은 O(n)입니다.

function solution(logs) {
  if (logs.length === 0) {
    return [-1, 0];
  }

  const events = [];

  for (const [start, end] of logs) {
    events.push([start, 1]);
    events.push([end, -1]);
  }

  events.sort((a, b) => {
    if (a[0] !== b[0]) return a[0] - b[0];
    return a[1] - b[1]; // -1 먼저, 1 나중
  });

  let current = 0;
  let bestCount = 0;
  let bestTime = -1;

  for (const [time, delta] of events) {
    current += delta;

    if (current > bestCount) {
      bestCount = current;
      bestTime = time;
    }
  }

  return [bestTime, bestCount];
}

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.