문제 소개
두 개의 정렬된 연결 리스트(linked list)가 주어졌을 때, 시작 노드부터 끝 노드까지 이동하면서 노드 값의 합이 가장 커지는 경로만으로 구성된 새로운 연결 리스트를 만들어야 합니다. 최종 결과 리스트는 두 입력 리스트에 속한 노드들을 모두 포함할 수 있습니다.
다만 결과 리스트를 생성하는 과정에서 한쪽 리스트에서 다른 쪽 리스트로 전환할 수 있는 지점은 오직 교차점, 즉 두 리스트에서 값이 서로 같은 노드뿐이라는 제약 조건이 있습니다. 또한 추가 메모리를 상수(constant) 크기만 사용해야 하므로, 새로운 리스트를 복사해 만드는 대신 기존 노드의 next 포인터를 재연결하는 방식으로 문제를 해결해야 합니다.
예시
입력이 다음과 같다고 가정해 보겠습니다.
[6, 8, 35, 95, 115, 125], [5, 8, 17, 37, 95, 105, 125, 135]
이때 원하는 출력은 아래와 같습니다.
[6, 8, 17, 37, 95, 115, 125, 135]
두 리스트는 8, 95, 125에서 교차하며, 각 교차점 사이 구간에서 합이 더 큰 쪽의 노드들을 선택하면 최대 합 경로가 완성됩니다.
알고리즘 접근 방법
핵심 아이디어는 두 리스트를 동시에 순회하면서 교차점 사이 구간별 합(res1, res2)을 계산하고, 합이 더 큰 구간의 노드들이 결과 경로에 오도록 이전 교차점 노드의 next 포인터를 다른 리스트 쪽으로 연결해 주는 것입니다. 절차는 다음과 같습니다.
result:= None 으로 초기화합니다.previous1:= a,current1:= a 로 설정합니다.previous2:= b,current2:= b 로 설정합니다.current1또는current2가 None이 아닌 동안 다음을 반복합니다.res1:= 0,res2:= 0 으로 초기화합니다.current1과current2가 모두 null이 아니고 두 노드의 데이터 값이 서로 다른 동안 다음을 반복합니다.current1.data < current2.data이면res1에current1.data를 더하고current1을 다음 노드로 이동합니다.그렇지 않으면
res2에current2.data를 더하고current2를 다음 노드로 이동합니다.
current1이 null이라면,current2가 null이 될 때까지 남은 노드의 값을res2에 계속 더합니다.current2가 null이라면,current1이 null이 될 때까지 남은 노드의 값을res1에 계속 더합니다.previous1 == a이고previous2 == b(첫 번째 구간)라면,res1 > res2일 때result:=previous1, 그렇지 않으면result:=previous2로 설정합니다.그 외의 경우에는
res1 > res2이면previous2.next:=previous1.next로, 그렇지 않으면previous1.next:=previous2.next로 변경하여 합이 큰 쪽 구간으로 경로를 연결합니다.previous1:=current1,previous2:=current2로 갱신합니다.current1이 null이 아니면 다음 노드로,current2가 null이 아니면 다음 노드로 각각 이동합니다.
반복이 끝나면
result의 내용을 순서대로 출력합니다.
Python 구현 예제
아래 코드를 통해 실제 동작을 확인해 보겠습니다.
class LinkedList(object): def __init__(self, data_set = []): self.head = None if len(data_set) > 0: for item in data_set: self.insert_node(item) class ListNode(object): def __init__(self, d): self.data = d self.next = None def insert_node(self, new_data): new_node = self.ListNode(new_data) new_node.next = self.head self.head = new_node def find_max_sum_list(self, a, b): result = None previous1 = a current1 = a previous2 = b current2 = b while current1 != None or current2 != None: res1 = 0 res2 = 0 while current1 != None and current2 != None and current1.data != current2.data: if current1.data < current2.data: res1 += current1.data current1 = current1.next else: res2 += current2.data current2 = current2.next if current1 == None: while current2 != None: res2 += current2.data current2 = current2.next if current2 == None: while current1 != None: res1 += current1.data current1 = current1.next if previous1 == a and previous2 == b: result = previous1 if (res1 > res2) else previous2 else: if res1 > res2: previous2.next = previous1.next else: previous1.next = previous2.next previous1 = current1 previous2 = current2 if current1 != None: current1 = current1.next if current2 != None: current2 = current2.next while result != None: print(result.data, end = ' ') result = result.next my_list1 = LinkedList([125,115,95,35,8,6]) my_list2 = LinkedList([135,125,105,95,37,17,8,5]) my_list1.find_max_sum_list(my_list1.head, my_list2.head)
참고: 위 코드의 insert_node() 메서드는 새 노드를 항상 head 바로 앞에 삽입하므로, 데이터를 역순으로 전달해야 오름차순 연결 리스트가 만들어집니다.
입력
[125,115,95,35,8,6], [135,125,105,95,37,17,8,5]
출력
6 8 17 37 95 115 125 135
정리
이 알고리즘은 두 리스트를 각각 한 번씩만 순회하므로 시간 복잡도는 O(n + m)이며, 포인터 변수 몇 개만 추가로 사용하므로 공간 복잡도는 O(1)입니다. 교차점에서만 리스트를 전환할 수 있다는 제약 조건을 활용해, 구간별 합을 비교하고 next 포인터만 재연결함으로써 상수 공간 안에서 최대 합 연결 리스트를 효율적으로 구성할 수 있습니다.