구간(interval) 리스트와 하나의 값 point가 주어졌을 때, 해당 지점에서 교차하는 구간의 개수를 구하는 프로그램을 만들어 보겠습니다. 각 구간 interval[i]는 [si, ei] 형태로 표현되며, si는 시작 시간, ei는 종료 시간을 의미합니다(시작과 종료 시간 모두 포함).
문제 이해하기
예를 들어, 구간 리스트가 [[2, 6], [4, 10], [5, 9], [11, 14]]이고 point가 5라고 가정해 봅시다. 이 경우 출력값은 3이 됩니다. 시점 5에서 [2, 6], [4, 10], [5, 9] 세 개의 구간이 해당 지점을 포함하고 있기 때문입니다.
해결 접근 방법
이 문제는 매우 직관적인 방법으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 교차 개수를 저장할 변수 count를 0으로 초기화합니다.
- 각 구간의 시작 시간 i와 종료 시간 j를 순회하면서 확인합니다.
- 만약 point가 i보다 크거나 같고, j보다 작거나 같다면 해당 구간이 지점을 포함하는 것이므로 count를 1 증가시킵니다.
- 모든 구간을 확인한 후 최종 count 값을 반환합니다.
파이썬 구현 코드
아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.
def solve(intervals, point):
count = 0
for i, j in intervals:
if point >= i and point <= j:
count += 1
return count
intervals = [[2, 6],[4, 10],[5, 9],[11, 14]]
point = 5
print(solve(intervals, point))입력
[[2, 6],[4, 10],[5, 9],[11, 14]], 5
출력
3
복잡도 분석
이 알고리즘은 모든 구간을 한 번씩 순회하므로 시간 복잡도는 O(n)입니다. 여기서 n은 구간의 개수입니다. 공간 복잡도는 추가 변수만 사용하므로 O(1)로 상수 공간이 필요합니다. 구간의 수가 많지 않은 경우에는 이 방법이 가장 간단하고 효율적인 해결책입니다.