2021-01-06] Remove Duplicates from Sorted List II

하루하루.. 꾸준히 쓴다는 것은 정말 어렵다.. 문제 푸는 것도 그렇고, 그것을 정리하여 블로그로 남기는 것까지 할라니

쉽지가 않다.. 그래도 5일만에 무너질수없으니 오늘도 문제를 풀어봅시다.

 

오늘의 문제:

leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

Remove Duplicates from Sorted List II - LeetCode

 

문제 자체는 쉽게 이해하였다!

Single Linked List를 줄테니 거기서 중복되는 값 모두를 지운 나머지만 남겨줘! 라는 문제ㅋㅋ

그래도 예시를 보며 다시한번 이해 해보자.

 

<예시 1~2>

주어진 Linked List안의 중복되는 값 ( 3, 4 )들을 모두 빼고 나머지만으로 구성된 Linked List를 만들면 된다.

물론 List 가 [1,1]이 주어진다면 output의 값은 None이 되는 것이다. ( 필자가 헤맨 부분이기도 함 )

 

자 그럼 문제는 어케 풀수있을까?

 

문제풀이 1차)

Linked List는 넘나 다루기 구찮고 힘든 것이라 느껴 List로 변형 후 답을 구하고 다시 Linked List 만든것.

 

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        ans = [] # Linked List값을 List로 변경하기 위한 초기 값
        pivot=head # Linked List를 copy하여 head의 값을 유지하고 pivot으로 사용
        if head == None: # 처음부터 값이 없거나 한개면 None이나 head를 리턴하면 끝!
            return None
        if pivot.next == None:
            return pivot
        while pivot.next != None: # Linked List에서 마지막값 빼고 방문
            ans.append(pivot.val) # 모든 값을 List로 변환하기
            pivot=pivot.next
        ans.append(pivot.val) # 나머지 마지막 값 추가
        temp=ans[0] # List의 첫번째 값
        same=False # 중복을 검사하기 위한 bool 값
        anslist=[] # 실제 답을 담을 List
        for i in range(1,len(ans)): # List의 두번째 값부터 비교하기 위해 1부터 시작
            if temp == ans[i]: # 값이 중복되면
                if temp in anslist: 
                    anslist.remove(temp) # 중복되는 값을 제거
                same=True
            else:
                if same:
                    same=False    
                else:
                    anslist.append(temp) # 값이 중복되지 않으면 anslist에 추가
            if i == len(ans)-1:
                if temp==ans[i]:
                    continue
                else:
                    anslist.append(ans[i])
            temp=ans[i]
        if len(anslist) < 1:
            return None
        else:
            for i in range(len(anslist)):
                if i == 0:
                    answer=ListNode(anslist[i]) # List를 Linked List 형식으로 만듬
                else:
                    pivot=answer
                    while pivot.next!= None:
                        pivot=pivot.next
                    pivot.next=ListNode(anslist[i])
            return answer

 

<문제풀이 1차의 성능>

 

문제풀이 2차)

위의 풀이는 약간 애매해서 다시 만들어본 중복된값만 찾은뒤 빼고 Linked List만드는 code

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head ==None:
            return None
        if head.next == None:
            return head
        # 마찬가지로 위에까지 None이나 Node가 한개면 None, head 반환
        pivot=head
        samelist=[] # 이번엔 중복되는 value list를 작성
        while pivot!=None:
            if pivot.next:
                if pivot.val == pivot.next.val:
                    if pivot.val not in samelist: # 중복되는 값이 한번만 들어가도록
                        samelist.append(pivot.val)
            pivot=pivot.next
        pivot=head
        ans=ListNode() # 답을 넣을 ListNode 생성
        while pivot!=None:
            if pivot.val in samelist: #Linked List를 돌면서 중복된 값이 발견되는 Node는 패스
                pivot=pivot.next
            else:
                temp=ListNode(pivot.val) # 찾은 중복되지 않는 Node를 ans ListNode에 append
                anspivot=ans
                print(temp)
                while anspivot.next != None:
                    anspivot=anspivot.next
                anspivot.next=temp
                pivot=pivot.next
        return ans.next # 초기화된 Node로 첫번째 dummy 값인 0이 들어가 next값을 전달한다.

<문제풀이 2차의 성능>

 

왜 더 구려졌지..? 메모리만 덜 잡아먹었구나.. 아직은 멀고만 알고리즘과 자료구조의 세계인듯..