Python으로 절단 구간과 겹치지 않는 구간 찾기

정렬되어 있고 서로 겹치지 않는 구간(interval) 목록과 하나의 '절단(cut)' 구간이 주어졌을 때, 기존 구간 중 절단 구간과 겹치는 부분을 모두 제거한 새로운 목록을 반환하는 프로그램을 만들어 보겠습니다.

예제로 이해하기

예를 들어 구간 목록이 [[2, 11], [13, 31], [41, 61]]이고 절단 구간이 [8, 46]이라고 가정해 봅시다. 절단 구간에 걸친 부분을 잘라내면 결과는 [[2, 8], [46, 61]]이 됩니다.

• [2, 11]은 8~11 부분이 잘려나가 [2, 8]만 남습니다.
• [13, 31]은 절단 구간 안에 완전히 포함되므로 사라집니다.
• [41, 61]은 41~46 부분이 잘려나가 [46, 61]만 남습니다.

풀이 접근 방법

다음 단계를 따르면 문제를 해결할 수 있습니다.

• 절단 구간의 시작점과 끝점을 각각 cut_start, cut_end로 저장합니다.
• 결과를 담을 빈 리스트 ans를 생성합니다.
• 각 구간(start, end)에 대해 아래 과정을 반복합니다.
  • max(cut_start, start) < min(end, cut_end)라면 두 구간이 겹치는 것이므로,
    • start < cut_start이면 남는 앞부분 [start, cut_start]를 ans에 추가합니다.
    • end > cut_end이면 남는 뒷부분 [cut_end, end]를 ans에 추가합니다.
  • 두 구간이 겹치지 않으면 원래 구간 [start, end]를 그대로 ans에 추가합니다.
• 모든 구간을 처리한 후 ans를 반환합니다.

구현 코드

class Solution:
   def solve(self, intervals, cut):
      cut_start, cut_end = cut
      ans = []
      for start, end in intervals:
         # 현재 구간이 절단 구간과 겹치는지 확인
         if max(cut_start, start) < min(end, cut_end):
            # 절단 지점 앞쪽에 남는 부분 추가
            if start < cut_start:
               ans.append([start, cut_start])
            # 절단 지점 뒤쪽에 남는 부분 추가
            if end > cut_end:
               ans.append([cut_end, end])
         else:
            # 겹치지 않으면 원래 구간 유지
            ans.append([start, end])
      return ans

ob = Solution()
intervals = [[2, 11], [13, 31], [41, 61]]
cut = [8, 46]
print(ob.solve(intervals, cut))

입력

[[2, 11], [13, 31], [41, 61]], [8, 46]

출력

[[2, 8], [46, 61]]

복잡도 분석

각 구간을 한 번씩만 확인하면 되므로 시간 복잡도는 O(n)입니다(n은 구간 목록의 길이). 공간 복잡도 역시 결과를 저장하는 데 필요한 O(n)입니다. 이 방식은 구간 수가 많아도 선형 시간 안에 빠르게 처리할 수 있다는 장점이 있습니다.