정렬된 두 연결 리스트 L1과 L2가 주어졌을 때, 두 리스트의 합집합(union)에 해당하는 새로운 정렬된 연결 리스트를 반환하는 프로그램을 만들어 보겠습니다. 합집합이란 두 리스트에 등장하는 모든 값을 포함하되, 양쪽에 공통으로 존재하는 중복 값은 한 번만 담는 것을 의미합니다.
예를 들어 입력이 다음과 같다면,
- L1 = [10, 20, 30, 40, 50, 60, 70]
- L2 = [10, 30, 50, 80, 90]
출력은 중복이 제거된 [10, 20, 30, 40, 50, 60, 70, 80, 90]이 됩니다.
문제 해결 접근 방식
두 리스트가 이미 정렬되어 있으므로, 재귀(recursion)를 이용해 앞에서부터 노드를 하나씩 비교하며 병합하면 됩니다. 핵심 아이디어는 다음과 같습니다.
- solve() 함수를 정의하고, L1과 L2를 인자로 전달합니다.
- L1이 비어 있으면 L2를 그대로 반환합니다.
- L2가 비어 있으면 L1을 그대로 반환합니다.
- L1의 값이 L2의 값보다 작으면:
- res := L1
- res.next := solve(L1.next, L2)
- L2의 값이 L1의 값보다 작으면:
- res := L2
- res.next := solve(L2.next, L1)
- 두 값이 같으면:
- res := L1
- res.next := solve(L1.next, L2.next) → 두 리스트 모두 한 칸씩 전진시켜 중복을 제거합니다.
- 마지막으로 res를 반환합니다.
특히 두 값이 같은 경우에 양쪽 리스트의 포인터를 동시에 이동시키는 부분이 합집합에서 중복을 걸러내는 핵심입니다. 이 알고리즘의 시간 복잡도는 두 리스트의 길이를 각각 n, m이라 할 때 O(n + m)입니다.
구현 예제
class ListNode:
def __init__(self, data, next = None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_list(head):
ptr = head
print('[', end = "")
while ptr:
print(ptr.val, end = ", ")
ptr = ptr.next
print(']')
class Solution:
def solve(self, L1, L2):
if not L1:
return L2
if not L2:
return L1
if L1.val < L2.val:
res = L1
res.next = self.solve(L1.next, L2)
elif L2.val < L1.val:
res = L2
res.next = self.solve(L2.next, L1)
else:
res = L1
res.next = self.solve(L1.next, L2.next)
return res
ob = Solution()
L1 = make_list([10,20,30,40,50,60,70])
L2 = make_list([10,30,50,80,90])
print_list(ob.solve(L1, L2))입력
[10,20,30,40,50,60,70], [10,30,50,80,90]
출력
[10, 20, 30, 40, 50, 60, 70, 80, 90]
정리
이처럼 정렬된 연결 리스트의 합집합은 재귀적 병합 기법으로 간단하게 구현할 수 있습니다. 빈 리스트 처리, 값 비교, 중복 제거 세 가지 조건만 명확히 하면 되며, 코드 역시 직관적이라 초보자에게도 좋은 연습 문제입니다.