본문 바로가기
IT/Python

파이썬 알고리즘 - 링크드리스트(LinkedList)에서 중복 제거하기

by SimpleWorld StoryFeed 2019. 10. 25.

개발자 면접 트레이딩 - 파이썬 알고리즘 문제(6)

 

 


(1). 개발자 면접 트레이닝 - 링크드리스트에서 중복되는 노드 삭제(Delete) 알고리즘


① 링크드리스트는 다음 노드의 위치를 가르키고 있는 포인트 보유

파이썬 클래스 Next 변수 활용

③ 첫 번째 노드(Node)의 위치를 지정하는 것이 중요ㅛ

④ 예를들어 [3, 4, 5, 6, 7, 7, 8, 9, 9]  는 -> [3, 4, 5, 6, 7, 8, 9] 출력

 

 

(2). 소스 코드


PYTHON

#remove_dup_linkedlist.pyimport unittestclass Node:    def __init__(self, item):        self.val = item        self.next = Noneclass LinkedList:    def __init__(self, item):        self.head = Node(item)    def add(self, item):        cur = self.head        while cur.next is not None:            cur = cur.next        cur.next = Node(item)    def delete_duplicate(self):        cur = self.head        dict = {}        prev = None        while cur is not None:            if cur.val in dict:                prev.next = cur.next            else:                dict[cur.val]= True                prev = cur            cur = cur.next    def printlist(self):        cur = self.head        res = []        while cur is not None:            res.append(cur.val)            cur = cur.next        return str(res)class LinkedListTest(unittest.TestCase):    def test(self):        ll = LinkedList(3)        ll.add(4)        ll.add(5)        ll.add(6)        ll.add(4)        ll.add(7)        ll.add(4)        ll.add(6)        ll.add(6)        ll.delete_duplicate()        self.assertEqual("[3, 4, 5, 6, 7]", ll.printlist())        print(ll.printlist())unittest.main()

 

(3). 소스 코드 분석


① 14 라인 : 헤드(Head) 노드 선언

② 19 라인 : 다음 노드의 주소(Next)가 None이 아닐 경우 다음 노드 연결

③ 30 라인 : 중복되는 Key 가 존재할 경우 중복되는 노드의 주소 연결을 건너뛴다.

④ 38 라인 : 중복 제거된 링크드리스트(LinkedList) 확인 출력

⑤ 62 라인 : assertEqula 단위 테스트 함수를 사용하여 입력 결과와 출력결과를 비교

 


LinkedList(링크드리스트)

 관련 알고리즘 문제는 자주 활용, 출제 되므로 

Java, C 

 등으로 작성해보자.

 

참고로 이 예제는

파이썬

Set

메소드로 쉽게 해결 가능하다.


(4

).

실행결과1 - 단위테스트 정상 출력(비교 같을 경우)

 

 

(5

).

실행결과2 - 단위테스트 에러 출력(비교 다를 경우)






저작자표시

동일조건

  • 네이버 블러그 공유하기
  • 페이스북 공유하기
  • 트위터 공유하기
  • 구글 플러스 공유하기
  • 카카오스토리 공유하기

댓글0