프로그래밍 문제에서 자주 만나게 되는 유형 중 하나는 구간(Interval) 데이터를 다루는 것입니다. 이번 글에서는 여러 개의 근무 시간 구간과 하나의 특정 시간이 주어졌을 때, 그 시점에 실제로 근무 중인 프로그래머가 몇 명인지 계산하는 방법을 알아보겠습니다.
문제 정의
구간 목록과 하나의 시간 값(time)이 입력으로 주어집니다. 각 구간은 [시작, 종료] 형태로 표현되며, 해당 프로그래머가 일한 시간대를 나타냅니다. 우리의 목표는 주어진 시간에 근무 중이던 프로그래머의 수를 구하는 것입니다.
예를 들어 입력이 다음과 같다고 가정해 봅시다.
- interval = [[2, 6], [4, 10], [5, 9], [11, 14]]
- time = 5
이 경우 출력은 3이 됩니다. 시간 5일 때 [2, 6], [4, 10], [5, 9] 구간에 속한 세 명의 프로그래머가 모두 근무 중이기 때문입니다.
해결 접근법
이 문제는 매우 직관적인 방법으로 해결할 수 있습니다. 핵심 아이디어는 각 구간을 순회하면서 해당 시간이 구간 범위에 포함되는지 확인하는 것입니다. 알고리즘은 다음과 같습니다.
- 카운터(count)를 0으로 초기화합니다.
- 모든 구간을 하나씩 순회하면서 다음 조건을 검사합니다.
- 구간의 시작 시간 ≤ time 이고, 구간의 종료 시간 ≥ time 이면 count를 1 증가시킵니다.
- 순회가 끝나면 count 값을 반환합니다.
Python 구현 예제
아래 코드를 통해 위 로직을 더 쉽게 이해할 수 있습니다.
class Solution:
def solve(self, intervals, time):
count = 0
for interval in intervals:
if interval[0] <= time and interval[1] >= time:
count += 1
return count
ob = Solution()
interval = [[2, 6], [4, 10], [5, 9], [11, 14]]
time = 5
print(ob.solve(interval, time))입력 및 출력 결과
입력:
[[2, 6], [4, 10], [5, 9], [11, 14]], 5
출력:
3
복잡도 분석
이 알고리즘은 구간 목록을 한 번만 순회하므로 시간 복잡도는 O(n)입니다(n은 구간의 개수). 추가 메모리를 거의 사용하지 않으므로 공간 복잡도는 O(1)로 매우 효율적입니다.
만약 구간 목록이 매우 크고 동일한 질의를 반복적으로 수행해야 한다면, 누적합(Cumulative Sum)이나 스위핑(Sweeping) 기법을 활용해 각 시점별 근무 인원을 미리 계산해 두는 최적화도 가능합니다. 하지만 단일 질의 기준으로는 위의 단순 반복문 방식이 가장 깔끔하고 효율적인 선택입니다.