안녕하세요.
요즘 Cracking the coding interview 라는 책을 통해서 공부하고 있습니다.
연결 리스트 문제 중에 비정렬 연결 리스트에서 중복 문자열을 제거하는 코드 문제를 파이썬으로 해결해보려고 합니다.
+ 임시 버퍼를 사용하는 방법과 임시 버퍼를 사용하지 않는 방법 두가지 모두 코드를 작성하여 봤습니다.
일단 값과 다음 노드를 가르키는 객체인 Node 객체를 만듭니다.
복사 가능한 코드
class Node:
def __init__(self, value, next_node):
self.value = value
self.next = next_node
그리고 LinkedList 를 구현합니다.
여기서 설명은 원소를 추가, 삭제 ,조회 등을 구현하는 것은 설명하지 않고 중복 문자열을 제거하는 코드에 대해서만 설명을 할 것 입니다.
첫번째 함수는 임시 버퍼인 dictonary를 사용해서 O(n)의 시간 복잡도로 문제를 해결했습니다.
순회하면서 dictonary에 value를 넣고 중복되는 값이 있는지 체크하면서 중복된 경우 중복된 노드를 삭제하고 전 노드와 중복 노드가 가리키는 노드를 연결해서 문제를 해결했습니다.
두 번째 문제인 임시버퍼를 사용하지 않는 경우는 하나의 node 변수를 추가해서 시간 복잡도 O(n**2)의 시간복잡도로 하나의 값을 가지고 있으면서
순회하면서 중복된 값을 찾아서 제거하는 방법을 사용했습니다.
전체 LinkedList 코드입니다.
class LinkedList:
def __init__(self):
self.head = Node(None, None)
self.cur = None
def add(self, value):
self.cur = self.head
while self.cur.next is not None:
self.cur = self.cur.next
self.cur.next = Node(value, None)
def _remove(self, cur):
cur.next = cur.next.next
def remove(self, value):
self.cur = self.head
while self.cur.next is not None:
if self.cur.next.value == value:
self._remove(self.cur)
return value
self.cur = self.cur.next
raise Exception("value not found")
def show_all(self):
self.cur = self.head.next
while self.cur is not None:
print(self.cur.value)
self.cur = self.cur.next
def remove_duplicate_word(self):
self.cur = self.head
temporary_buffer = {}
while self.cur.next is not None:
if temporary_buffer.get(self.cur.next.value) is not None:
self._remove(self.cur)
else:
temporary_buffer[self.cur.next.value] = 0
self.cur = self.cur.next
# 임시 버퍼 사용 x
def remove_duplicate_word_without_buffer(self):
runner = self.head.next
self.cur = self.head
while runner is not None:
self.cur = runner
while self.cur.next is not None:
if runner.value == self.cur.next.value:
self._remove(self.cur)
else:
self.cur = self.cur.next
runner = runner.next
해당 책의 문제들을 파이썬으로 해결한 코드를 Github에 올릴 예정입니다.
repository가 만들어지면 공유 드리도록 하겠습니다.