알고리즘수업에서 Linked List 구현하는 것이 숙제로 나온 기념으로 비슷한 문제를 풀어보았다.

• Day 15: Linked List 문제 보러가기

문제 풀이

• Node 클래스가 에디터에 준비되어 있다. Node 객체는 정수 데이터인 data를 값으로 가지고, next라는 포인터로 다음 노드를 가리킨다.
• 첫번째 노드를 가리키는 pointer인 head와, data를 매개변수로 가지고 있는 Node insert 함수를 완성시켜라.

문제 해석

Task

• data 인수를 받아 새로운 노드를 생성하고 이를 head 매개변수로 지정된 linked list 끝에 삽입하는 insert 함수를 완성시켜라.
• 새로운 노드가 추가되면 참조값을 head node로 리턴해라. (빈 linked list의 head는 null이다.)

Input Format

• 첫번째 줄은 삽입할 요소의 개수를 나타내는 T
• T 이후에 오는 T개의 줄은 linked list의 끝에 삽입할 정수값

Output Format

• head node로의 참조값을 리턴해라

문제 풀이

이미 주어진 코드 해석

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

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

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

    def insert(self,head,data): 
    #Complete this method

• Node 클래스는 data를 인수로 받아 자기자신의 data를 프로퍼티로 갖고, 처음 생성되면 None을 가리키는 포인터를 next라는 프로퍼티로 갖는 인스턴스를 생성한다.
• Solution 클래스의 첫 메서드인 display는 head를 인수로 받는데, 이는 해당 linked list에 대한 참조값이다. display를 호출하면 head로 지정된 해당 linked list의 모든 데이터를 스페이스를 하나씩 넣어 출력해준다.
• 나의 작업은 insert라는 메서드를 완성시키는 것인데, 이는 head와 data를 인수로 받는다.

1
2
3
4
5
6
7

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

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

시행착오

• 알고리즘 수업에서 숙제로 내준 linked list 구현이 크게 도움이 되었다.
• 에디터에 미리 작성된 head = mylist.insert(head, data)를 못보고, 그리고 제대로 문제를 읽지 않아서 return문을 빼놓았더니 동작을 전혀 하지 않아서 애먹었다. 문제를 잘 읽자.

코드 작성하기

1
2
3
4
5
6
7
8
9

def insert(self,head,data): 
    if head == None:
        return Node(data)
    else:
        curr = head
        while curr.next != None:
            curr = curr.next
        curr.next = Node(data)
        return head

• 빈 배열, 곧 head가 None일 경우에는 처음으로 생성되는 노드를 Node 클래스를 통해 data를 인수로 주어 만들고(Node(data)) 만든 instance를 할당한다.
• head가 None이 아닌 경우에는 head로부터 하나씩 next를 찍으면서 next 값이 None인 경우에는 새로 들어온 data를 인수로 받아 만든 Node instance를 next에 할당해준다.
• 두 경우 다 업데이트된 head를 리턴해준다.

느낀 점

• 자료구조 배우기 전에 도무지 이해가 가지 않아서 몇번을 실패했던 문제인데 이렇게 성공하니까 기분 째진다.
• Linked List는 뭔가 물고 물리고 올챙이 같아서 귀엽다.