닫힌 구간(closed interval)으로 이루어진 두 개의 리스트가 있다고 가정해 보겠습니다. 각 리스트는 내부적으로 서로 겹치는 구간이 없으며, 시작 지점을 기준으로 비내림차순(오름차순과 유사하되 같은 값을 허용)으로 정렬되어 있습니다. 이때 해야 할 작업은 두 구간 리스트에서 서로 겹치는 부분을 모두 찾아, 비내림차순으로 정렬된 형태로 반환하는 것입니다.
예를 들어 입력이 다음과 같다면,
inv1 = [[50, 100], [190, 270], [310, 330]]
inv2 = [[40, 120], [180, 190]]
출력 결과는 다음과 같습니다.
[[50, 100], [190, 190]]
문제 해결 접근 방식
이 문제는 투 포인터(Two Pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 두 리스트를 동시에 순회하면서 각 단계마다 겹치는 구간을 계산하고, 끝점이 더 작은 쪽의 포인터를 앞으로 이동시키는 방식입니다. 구체적인 절차는 다음과 같습니다.
- 결과를 저장할 빈 리스트 ans를 생성합니다.
- 포인터 i와 j를 각각 0으로 초기화합니다(각각 A와 B의 인덱스 역할).
- i가 A의 길이보다 작고 j가 B의 길이보다 작은 동안 다음을 반복합니다.
- start := max(A[i]의 시작점, B[j]의 시작점)
- end := min(A[i]의 끝점, B[j]의 끝점)
- 만약 start <= end라면 두 구간이 실제로 겹치는 것이므로 [start, end]를 ans에 추가합니다.
- A[i]의 끝점이 B[j]의 끝점보다 작으면 i를 1 증가시키고, 그렇지 않으면 j를 1 증가시킵니다.
- 반복이 종료되면 ans를 반환합니다.
핵심 아이디어는 간단합니다. 두 구간의 교집합은 '시작점 중 큰 값'부터 '끝점 중 작은 값'까지의 범위이며, 이 범위가 유효한 경우(start <= end)에만 결과에 포함됩니다. 이후 끝점이 앞선 구간의 리스트 포인터를 이동시켜 다음 후보를 검사합니다.
예제 코드
class Solution:
def solve(self, A, B):
ans = []
i = 0
j = 0
while i < len(A) and j < len(B):
start = max(A[i][0], B[j][0])
end = min(A[i][1], B[j][1])
if start <= end:
ans.append([start, end])
if A[i][1] < B[j][1]:
i += 1
else:
j += 1
return ans
ob = Solution()
inv1 = [[50, 100],[190, 270],[310, 330]]
inv2 = [[40, 120],[180, 190]]
print(ob.solve(inv1, inv2))
입력
[[50, 100],[190, 270],[310, 330]], [[40, 120],[180, 190]]
출력
[[50, 100], [190, 190]]
복잡도 분석
이 알고리즘의 시간 복잡도는 O(n + m)입니다. 여기서 n과 m은 각각 A와 B 리스트의 길이입니다. 매 반복마다 최소 하나의 포인터가 앞으로 이동하기 때문에 전체 순회 횟수는 두 리스트 길이의 합을 넘지 않습니다. 공간 복잡도는 결과를 저장하는 데 필요한 만큼, 최악의 경우 O(n + m)입니다.