⭐️ LeetCode 알고리즘 풀이 (with Python)

# Remove Duplicates from Sorted List II

[Quetion]

LeetCode 82. Remove Duplicates from Sorted List II

📌 접근법

[문제 이해]

• 주어진 링크드 리스트에서 중복되는 노드는 전부 삭제한 후 링크드 리스트 반환
• ex) [1-2-3-3-4] ---> [1-2-4]

조금 복잡하지만 내가 생각한 구현 흐름은 다음과 같다.

• Linked List의 데이터인 val을 리스트에 모두 담는다.
• 리스트에 담긴 값을 key, 중복되는 개수를 value로 하는 HashTable 생성
• HashTable에서 value가 1 초과인 key는 모두 삭제
• 남아있는 key를 다시 리스트에 담고, 리스트 값을 기준으로 링크드 리스트로 변환

💻 구현

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # num에 Linked List 데이터 담기
        num=[]
        while head:
            num.append(head.val)
            head = head.next
        
        # num 값을 key, 중복 개수를 value로 하는 dict 
        num_dict={}
        for i in num:
            num_dict[i] = num_dict.get(i, 0) + 1
        
        # value > 1인 key 삭제
        duplicate = [key for key, value in num_dict.items() if value > 1]
        for i in duplicate:
            del num_dict[i]
        
        # key 기준 다시 리스트로 변경, 링크드 리스트로 재생성
        num = [i for i in num_dict.keys()]
        result = ListNode()
        curr = result
        i=0
        while len(num) > i:
            node = ListNode(num[i])
            curr.next = node
            curr = node
            i+=1
        return result.next

Runtime: 42ms | Memory: 16.2MB
LeetCode 코드 중 Runtime 80%, Memory 78% 해당하는 결과

📌 로직 핵심

• Linked List 데이터를 추출
• HashTable 활용 중복 데이터 제거
• 다시 Linked List로 재생성

---

📝 Remove Duplicates from Sorted List II 회고

• 시간복잡도와 공간복잡도는 모두 O(N)이다. 반복문이 많이 사용되긴 했지만, 최대 Linked List의 Node 개수 만큼만 반복하므로 O(N)만큼의 시간복잡도와 공간복잡도가 나오게 된 것이다.

• 리스트에 데이터를 담는 과정과 dict를 생성하는 과정을 합칠 수 있고, 중복된 데이터를 삭제하고 다시 리스트로 바꾸지 않고도 Linked List로 변경할 수 있어서 코드를 조금 변경해보았다.

# 수정된 코드
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        num_dict = {}
        while head:
            num_dict[head.val] = num_dict.get(head.val, 0) + 1
            head = head.next
            
        duplicate = [key for key, value in num_dict.items() if value > 1]
        for i in duplicate:
            del num_dict[i]
        
        result = ListNode()
        curr = result
        for i in num_dict:
            node = ListNode(i)
            curr.next = node
            curr = node
        return result.next

성능상 큰 차이는 없지만 리스트에 Linked List의 데이터를 담는 과정을 삭제하고, key값을 리스트에 담는 과정을 줄임으로써 반복문 2개를 제거했다.

문제를 해결하고, 다른 솔루션을 찾아보니 재귀적으로 해결한 솔루션이 가장 신기하게 느껴졌고, HashTable 방법을 활용한 코드도 많다는 것을 알게 되었다.

아직 Linked List 자체를 조작하는 것에 익숙하지 않아서 더 어렵게 느껴지는 것 같다.