Computer Engineering/Data Structure

파이썬 비정렬 연결 리스트에서 중복 문자열을 제거하는 코드 (with Cracking the coding interview)

jordan.bae 2018. 12. 31. 12:21



안녕하세요.


요즘 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가 만들어지면 공유 드리도록 하겠습니다.







반응형