Linked List의 심화 문제를 풀어보자.

• Day 24: More Linked Lists 문제 보러가기

문제 풀이

문제 해석

Task

• Node 클래스가 에디터에 준비되어 있다. Node 객체는 정수 데이터인 data를 값으로 가지고, next라는 포인터로 다음 노드를 가리킨다.
• removeDuplicates라는 함수가 정의되어 있는데, linked list의 head 노드를 인수로 주면 중복되는 값을 갖는 노드를 제거하고 업데이트된 리스트를 리턴하는 동작을 하도록 완성시켜라.
• head가 가리키는 값이 null, 즉 빈 linked list가 주어질 수도 있다.

Input Format

• 첫번째 줄은 앞으로 올 node에 넣을 값의 개수 T
• T 이후에 오는 N개의 줄은 linked list에 삽입할 정수값

Output Format

• 중복된 값을 제거한 리스트가 업데이트된 head를 리턴하게 코드를 완성하기만 하면 에디터에 이미 짜여진 코드가 알아서 출력할 것

문제 풀이

이미 주어진 코드 해석

1
2
3
4

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

• 지난 블로그 글과 동일하게 Node 클래스는 data를 인수로 받아 자기자신의 data를 프로퍼티로 갖고, 처음 생성되면 None을 가리키는 포인터를 next라는 프로퍼티로 갖는 인스턴스를 생성한다.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution: 
    def insert(self,head,data):
            p = Node(data)           
            if head==None:
                head=p
            elif head.next==None:
                head.next=p
            else:
                start=head
                while(start.next!=None):
                    start=start.next
                start.next=p
            return head  

• Solution 클래스의 첫 메서드인 insert는 이전 블로그 글(Day 15 - Linked List)에서 내가 만들어야했던 메서드이다. 메서드의 인수로 받은 data를 새로운 Node 객체 생성 시 인수로 넘겨 p를 만든다. head가 아무것도 가리키지 않으면 head에 p를 할당하고, head가 있긴 한데 가리키는 next가 None이면 head의 next가 p를 가리키도록 하고, 그렇지 않은 경우에 linked list를 앞에서부터 돌면서 next가 None인 노드에 가서 붙는다.
  • 지난 글의 내 코드와 비교해보니 p에 Node객체를 만들어 할당해두고 시작하는 건 좋아보인다. 근데 elif 문이 없어도 head의 next가 None이면 else문과 동일하게 동작할텐데 왜 굳이 따로 떼어놓은 것일까…?
  • 아무튼 업데이트된 리스트의 head를 리턴한다.

1
2
3
4
5

def display(self,head):
    current = head
    while current:
        print(current.data,end=' ')
        current = current.next

• Solution 클래스의 두번째 메서드 display도 바로 전 블로그 글과 동일.
  • head를 인수로 받는데, 이는 해당 linked list의 첫 노드를 가리키는 참조값이다. display를 호출하면 head로 지정된 해당 linked list의 모든 데이터를 스페이스를 하나씩 넣어 출력해준다.
• 나의 작업은 insert라는 메서드를 완성시키는 것인데, 이는 head와 data를 인수로 받는다.

1
2
3
4
5
6
7
8

mylist= Solution()
T=int(input())
head=None
for i in range(T):
    data=int(input())
    head=mylist.insert(head,data)    
head=mylist.removeDuplicates(head)
mylist.display(head);

• insert 메서드 아래 에디터에서 준비한 코드이며 이것도 지난 블로그 글과 동일한데, removeDuplicates라는 메서드를 한번 실행시킨다는 것만 다르다.
  • mylist라는 변수에 Solution 클래스를 생성해 할당
  • 첫 줄로 들어오는 데이터 개수를 T라는 변수에 할당
  • T번만큼 for문을 돌면서 data라는 변수에 input을 받고, mylist에 insert 메서드를 호출하면서 head 참조값과 data를 인수로 준다.
  • 첫 head는 None이라는 점에 유의
  • removeDuplicates라는 메서드를 호출
  • display에 head를 넣어 출력해준다.

시행착오

• 이 문제는 줄글로 pseudocoding을 계속 했는데도 도저히 모르겠어서 반나절을 고생하다가 그림을 그려서야 겨우 풀었다. 기념으로 그림 첨부(아래)
• current.data == current.next.data의 결과에 따라서 서로 다른 동작을 하면서 while문을 돌았어야 하는데, 그 구조를 파악못해서 한참 헤맸다.

코드 작성하기

1
2
3
4
5
6
7
8
9
10
11

def removeDuplicates(self,head):
    if head == None:
        return head
    else:
        current = head
        while current.next != None:
            if current.data == current.next.data:
                current.next = current.next.next
            else:
                current = current.next
        return head          

• 먼저 head가 None인 경우에는 바로 head를 리턴해준다.
• 그렇지 않은 경우 current라는 변수에 head를 할당하고, current를 돌면서 next가 None을 가리키지 않는 경우마다의 동작을 지정한다.
• 현재의 노드가 가진 값이 다음 노드의 값과 같은 경우: 값이 같은 다음노드를 삭제하는데, 삭제는 곧 연결을 끊고 그다음 노드를 가리키도록 해주는 것이므로 current.next = current.next.next
  • 그다음에 다시 current.next가 None인지 확인한 후 같은 동작을 하게 해야하니까 current.next != None을 while문으로 돌린다.
• 현재 노드와 다음 노드의 값이 다른 경우: 그 다음 노드로 이동.
  • 이동 후 current.next가 None인지 확인하면서 같은 동작을 반복
• current.next가 None이면 비교할 노드가 더이상 없는 거니까 head를 리턴

느낀 점

• pseudocoding 줄글로 하면서 몇시간을 고민했는데 그림 하나 그리니까 쉽게 풀려서 허탈. 진작 그릴걸… 그래도 submit 성공하니까 기분 좋다.
• 이전 블로그 글에서 Linked List는 뭔가 물고 물리고 올챙이 같아서 귀엽다고 한 말 취소. 너무 어렵다.