2.1 중복 없애기

문제 

정렬되어 있지 않은 연결 리스트가 주어졌을때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성하라 

[연관문제] 임시 버퍼를 사용할 수 없다면 어떻게 풀까?

 

해결법

1. 중복되는 원소를 hash table로 추적해 나가며, 중복원소를 제거 

class Node:
    def __init__(self, dataval=None):
        self.data = dataval
        self.next = None

def Solution(node):
    data_set = set()
    prev = None
    
    while node is not None:
        if node.data in data_set:
            prev.next = node.next
        else :
            set.add(node.data)
            prev = node
        node = node.next
    return

배운점

해법에 HashSet과 같은것을 python에서 찾아보다가 python에서 set은 dictionary로 만들어진 자료구조기 때문에 find작업이 O(1)으로 같은 기능을 나타낸다는 것을 알아냈다.

또한 너무 쉽게 생각하고 짜다가 node.next = node.next.next 라는 말도안되는 코드를 짤 뻔 하며 prev 변수의 필요성을 생각하지 못했는데 linked list에서 현재노드와 이전노드 다음노드를 잘 생각하면서 코드를 만들어야겠다는 반성을 했다.

 

2. (버퍼가 없을때) Runner 기법을 이용한다

class Node:
    def __init__(self, dataval=None):
        self.data = dataval
        self.next = None

def Solution(node):
    cur_node = node
    runner_node = None
    while  cur_node is not None:
        runner_node = cur_node
        while runner_node is not None:
            if runner_node.next.data == cur_node.data :
                runner_node.next = runner_node.next.next
            else :
                runner_node = runner_node.next
        cur_node = cur_node.next
    return