겹치지 않게 고르는 최대 세션 수
자바스크립트 코딩테스트 문제로 greedy 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
세션 시간 구간이 담긴 배열 sessions가 주어질 때, 서로 겹치지 않게 참석할 수 있는 세션의 최대 개수를 반환하는 solution 함수를 작성하세요.
각 세션은 [start, end] 형태이며, end 시각과 다음 세션의 start 시각이 같다면 겹치지 않는 것으로 봅니다.
예를 들어 [1, 3] 세션이 끝난 직후 [3, 5] 세션에 바로 참석할 수 있습니다.
제한사항
sessions는 길이 1 이상 100,000 이하의 배열입니다.- 각 세션은
[start, end]형태의 정수 배열입니다. start < end를 만족합니다.start,end는-1,000,000이상1,000,000이하의 정수입니다.- 한 번에 하나의 세션에만 참석할 수 있습니다.
- 끝나는 시각과 시작 시각이 같으면 이어서 참석할 수 있습니다.
예시
- 입력:
[[-1, 1], [1, 3], [2, 4], [3, 5]]→ 출력:3 - 입력:
[[1, 4], [2, 3], [3, 5], [0, 7], [5, 6]]→ 출력:3 - 입력:
[[1, 2], [2, 3], [3, 4], [4, 5]]→ 출력:4
힌트
- 많은 세션을 고르려면, 현재 시점에서 가장 빨리 끝나는 세션을 우선 선택하는 전략을 떠올려 보세요.
- 시작 시각 순서보다 종료 시각 순서가 더 중요할 수 있습니다.
- 한 번 세션을 선택했다면, 그다음에는 이전 종료 시각 이상에서 시작하는 세션만 고를 수 있습니다.
해설
이 문제의 핵심은 앞으로 더 많은 세션을 남겨 두는 선택이 무엇인지 생각하는 것입니다.
직관적으로는 빨리 시작하는 세션이나 길이가 짧은 세션을 고르고 싶을 수 있지만, 항상 최적은 아닙니다. 가장 안정적인 전략은 종료 시각이 빠른 세션부터 선택하는 greedy 방식입니다.
왜 종료 시각이 빠른 세션을 골라야 할까?
어떤 세션을 하나 선택하면 그 시간 동안은 다른 세션을 고를 수 없습니다. 이때 더 일찍 끝나는 세션을 선택하면, 이후에 선택할 수 있는 시간 구간이 더 많이 남습니다. 즉, 미래 선택지를 가장 덜 막는 선택이 됩니다.
예를 들어 [[1, 4], [2, 3], [3, 5]]가 있다면:
[1, 4]를 먼저 고르면 이후 선택 폭이 줄어듭니다.[2, 3]을 먼저 고르면 그다음[3, 5]도 고를 수 있습니다.
풀이 방법
- 세션들을 종료 시각 오름차순으로 정렬합니다.
- 종료 시각이 같다면 시작 시각이 빠른 것부터 보아도 됩니다.
lastEnd를 아주 작은 값으로 두고 시작합니다.- 정렬된 세션을 앞에서부터 보면서,
- 현재 세션의
start가lastEnd이상이면 선택합니다. - 선택했다면 개수를 1 늘리고
lastEnd를 현재end로 갱신합니다.
- 현재 세션의
- 끝까지 순회한 뒤 선택한 개수를 반환합니다.
왜 이 방법이 맞을까?
종료가 가장 빠른 세션을 선택하면, 같은 시점까지 가능한 다른 선택보다 이후 구간을 가장 넓게 남길 수 있습니다. 이 선택을 반복해도 항상 손해 보지 않으므로 greedy 전략이 성립합니다.
시간 복잡도
- 정렬:
O(n log n) - 한 번 순회:
O(n)
따라서 전체 시간 복잡도는 O(n log n)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.