(간단한 코드)리트코드 83. Remove Duplicates from Sorted List

 

우선 Duplicate는 "중복"이라는 의미로, 알고리즘 문제를 풀다보면, 자주 등장하는 녀석이다.

 

연결 리스트가 뭔지는 많은 사람들이 알겠지만, 어떤 구조로 되어 있는지는 잘 모르는 사람들이 많다.

linked list 연결 리스트는 아래와 같이 만들어진다.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 1->1->2->3->3->4 순서로 되어 있는 연결 리스트는 다음과 같이 만들어진다.

head = ListNode(1, ListNode(1,ListNode(2,ListNode(3,ListNode(3,ListNode(4))))))
cur = head
print(head.val) # 1
print(head.next.val) # 1
print(head.next.next.val) # 2
print(head.next.next.next.val) # 3
print(head.next.next.next.next.val) # 3
print(head.next.next.next.next.next.val) # 4

 

ListNode라는 클래스 안에 ListNote를 넣는 형식으로, 양파 처럼 한층 한층이 만들어진다.

연결 리스트에서 val은 현재 숫자, next는 다음 숫자에서 끝에 있는 숫자를 가리키틑 '일종의 리스트 -> ListNote(어쩌구저쩌구)'이다.

 

그럼에도 감이 잘 안잡힌다면, 연결리스트에 관한 문제만 10개 풀면, 대충 무엇을 해야 할지 감이 잡히고, 재귀함수에 관해 10문제를 보고, 클래스란 무엇인가에 대해 다시 보고, 그 다음에 다시 연결 리스트를 보면 딱 지금 내 상태가 된다고 생각한다(잘은 설명을 못하지만, 누군가에게 설명하려고 노력하는 단계는 된다는 뜻이다).

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head

        while cur and cur.next:
            if cur.val != cur.next.val:
                cur = cur.next
            else:
                cur.next = cur.next.next
        
        return head

 

cur = head는 왜 해야 하는가?

여기서 우리는 결과값으로 연결 리스트의 "첫번째"부분을 반환해야 한다.

근데 head.next와 같은 형식으로 head를 만지면, 연결리스트의 마지막 요소를 반환하게 되므로, 

cur = head를 해준다. 

 

왜 코드에서는 cur을 만지는데 head의 요소도 변하나요?

>>> 이를 이해하기 위해서는 "컴파일"과 "하드웨어(메모리)"에 관한 지식을 어느정도 알아야 한다. 

메모리라고 하면, 단순히 SSD, RAM 을 떠나서, Cash Memory1, Cash Memory2, Cash Memory3 등 다양한 것을 공부하게 된다.

 

실제로 이거를 공부한다고, 지금 가지고 있는 의문이 "아!"하고 해결 되지는 않는다. 그저 하드웨어를 머리 깨질듯이 공부하고, "파이썬"이라는 언어가 어떻게 인식이 되는가 - ("컴파일러") -를 공부하고 다시 이를 보면, 대충 감이 잡힌다.

 

인문학 전공자는 울고 싶었다. 컴공이나 공학 관련된 전공 출신 사람들은 "학교에서 배운게 쓸모없다"고 푸념하는 사람들이 많은데, 이를 받아들이기 위해 얼마나 많은 도움이 되는지 자각을 못하는 것일뿐, 절대로 쓸모없지는 않다.

while cur and cur.next:
    if cur.val != cur.next.val: # 중복이 아니면, 다음걸로 넘어가기
        cur = cur.next
    else:
        cur.next = cur.next.next # 중복이면, 연결 리스트에서 제외

이 코드가 처음에는 정말로 익숙치 않았다. 그림으로 아래와 같다는 것을 정말로 많은 영상에서도 설명을 하지만, 그럼에도 받아들이는데 시간이 많이 걸렸다. 뭔가 어떤 지식을 알고 "아! 이래서 이렇구나!"가 아니라, 어느순간 "아, 그렇네, 당연한거였네"라는 식으로 받아들였다.

 

연결리스트는 나라불문 정말로 많은 사람들이 싫어하는 자료구조 중에 하나이다. 그러니 여기에 너무 많은 시간을 잡아먹지 말자, 이거 제대로 못한다고 다른거 못하는거 아니다.