연결 리스트(Linked List)는 각 노드가 두 개의 블록으로 구성된 선형 자료구조입니다. 하나의 블록에는 노드의 값 또는 데이터가 저장되고, 다른 블록에는 다음 노드의 주소가 저장됩니다.
이번 문제에서는 각 노드가 리스트 내의 다른 노드를 가리키는 랜덤 포인터(random pointer)를 가지고 있는 연결 리스트를 가정합니다. 이러한 원본 리스트와 동일한 구조를 가진 새로운 리스트를 만드는 작업을 수행해야 하며, 랜덤 포인터까지 그대로 복제하는 과정을 연결 리스트의 깊은 복사(Deep Copy)라고 부릅니다.
예시
입력:
5-> 2 -> 3 -> 7 ->4 ->
출력:
5-> 2 -> 3 -> 7 ->4 ->
설명: 원본 리스트의 각 노드 값을 새로운 노드에 복사하고, 원본 리스트의 랜덤 포인터 경로를 새 리스트에도 동일하게 적용하면 결과는 5-> 2-> 3-> 7-> 4-> 형태가 됩니다.
문제 해결 접근 방법
데이터와 랜덤 포인터를 함께 가진 연결 리스트를 완전히 복사하려면 다음과 같은 단계로 진행할 수 있습니다.
- 먼저, 원본 리스트의 각 노드 바로 뒤에 동일한 값을 가진 새 노드를 삽입합니다. 이렇게 하면 각 노드 뒤에 복제 노드가 생성됩니다.
- 그다음, 원본 리스트에서 랜덤 포인터가 가리키는 위치를 확인하고, 새로 생성된 노드의 랜덤 포인터를 알맞게 설정합니다.
- 마지막으로, 원본 리스트에 교차되어 있는 새 노드들을 분리해내면 깊은 복사된 연결 리스트가 완성됩니다.
알고리즘 단계
- 데이터 필드와 랜덤 노드의 주소를 가리키는 포인터를 가진 연결 리스트를 준비합니다.
- 함수 copyRandomList(head)는 원본 리스트의 헤드 노드를 입력으로 받아 깊은 복사된 리스트를 반환합니다.
- 헤드가 비어 있다면 리스트가 비어 있는 것이므로 헤드를 그대로 반환합니다.
- 원본 리스트의 각 노드 뒤에 동일한 값을 가진 새 노드를 삽입합니다.
- 원본 리스트의 랜덤 포인터를 복사하여 새 노드에 연결합니다. 즉, newnode->next = curr->randomPointer 형태로 설정합니다.
- 포인터와 데이터가 모두 설정된 새 노드들이 준비되면, 리스트를 분리하여 결과로 반환합니다.
구현 예제
class listnode:
def __init__(self, data):
self.data = data
self.next = None
self.random = None
def copyRandomList(head):
if head is None:
return head
# 원본 리스트의 각 노드 뒤에 동일한 값을 가진 새 노드를 삽입합니다.
curr = head
while curr != None:
new = listnode(curr.data)
new.next = curr.next
curr.next = new
curr = curr.next.next
# 새로 생성된 노드에 랜덤 포인터를 설정합니다.
curr = head
while curr != None:
curr.next.random = curr.random.next
curr = curr.next.next
# 새로 생성된 리스트를 원본 리스트에서 분리합니다.
curr = head
temp = head.next
while curr.next != None:
dummyHead = curr.next
curr.next = curr.next.next
curr = dummyHead
return temp
def printList(head):
curr = head
while curr != None:
print(curr.data, " ", curr.random.data)
curr = curr.next
head = listnode(1)
head.next = listnode(2)
head.next.next = listnode(3)
head.next.next.next = listnode(4)
head.next.next.next.next = listnode(5)
head.random = head.next.next
head.next.random = head
head.next.next.random = head.next.next.next.next
head.next.next.next.random = head.next.next.next.next
head.next.next.next.next.random = head.next
print("Original list:\n")
printList(head)
copiedList = copyRandomList(head)
print("\n Deep Copy of the List:")
printList(copiedList)위 코드를 실행하면 아래와 같은 결과가 출력됩니다.
실행 결과
Original list: 1 3 2 1 3 5 4 5 5 2 Deep Copy of the List: 1 3 2 1 3 5 4 5 5 2
출력 결과에서 확인할 수 있듯이, 복사된 리스트는 원본 리스트와 동일한 데이터 순서와 랜덤 포인터 구조를 정확하게 유지하고 있습니다. 이 방법은 추가 해시 맵 없이 O(n) 시간 복잡도와 O(1)의 추가 공간만으로 깊은 복사를 수행할 수 있다는 장점이 있습니다.