코딩: 말하기 듣기 쓰기-3

Remove Nth Node From End of List

링크드리스트는 내가 제일 쉽게 얕보면서 제일 못하는 부분이다. 잘하는줄 알고 보면 잘 못하고 있다. 즉, 구현을 못한다. 링크드리스트는 포인터라는 개념이 들어가있는데, 내가 그것에 대해 궁금해하다가 그래도 살짝 이해하게되었다. 그것을 기반으로, 링크드 리스트 문제에 대해서 오늘 풀게되었는데....이해하기가 어렵다. 우선 노드와 넥스트 개념이 머리에 잘 들어오지않았다. 아니 내말은 다음노드로가고 뭐고 다 알겠어. 그런데 왜 이상하게 코딩으로 안써지냐고. 그래서 코딩:말하기듣기쓰기 연습을 하기도하는데. 아무튼 많은분에게 모르는 것을 물어보았고, 친절하게 말씀해주셔서 이해가 되었다. 이제는 문제를 많이 접하면서 익숙해지는수밖에없다.

https://leetcode.com/problems/remove-nth-node-from-end-of-list

문제 보자마자 들었던 생각: 우선 조용히하고. 심호흡 한번 해주고. 동그라미와 화살표를 지긋이 바라본다. 여기서 느낌 가져가야한다. n에 나와있는 숫자. 뒤에서 두번째 느낌. 빨간색. 아웃. 바로아웃.
이느낌 살리고, 그러고 화살표 밑에 한번 봐주고 느낌있게 저거를 제거하려면 3에서 5로 화살표를 가주게 만들어야한다를 인지한다.
current, .next, head. 이거 세개 일단 제일중요하다.
현재위치, 현재위치가 가르키는 다음위치. 그리고 제일 첫번째로 시작하는 head. 느낌있게 시작한다. 이거를 이해시켜주신 우리 팀원분들. 고생이많다. 역시 난 사람복은 잘 타고났다.

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        '''
        Input: head = [1,2,3,4,5], n = 2
        Output: [1,2,3,5]
        '''
        
        current = head  # current node -> head
        # current = current.next #current moves to next node
        length = 0
        while current: 
            length += 1 #total linkedlist length 
            current = current.next
        
        current = head
        
        if n == length:
            head = head.next
            return head
        
        for i in range(length - n - 1): # arrive at the point before we meet goal position
            current = current.next #3
        
        current.next = current.next.next
            #4              #5
            
        return head

우선 현재위치 설정. 무조건 설정. 뭐든지 처음이 있으면 끝이있다. 처음위치 current = head. 이게 무슨말이냐면, 현재 위치의 첫번째. head로 정한다. 우선 첫번째로, 전체 1, 2, 3, 4, 5 를 다 돌았을 경우를 생각해본다. 그래서 while문에 넣는다. 단, 조건은 head에 무엇인가 있는 상태에서 끝까지 돌때. 이것을 돌 경우 1, 2, 3, 4, 5를 print해보면 출력해보고, 결국에 계속 다음을 가르키게되는데 5 다음은 None. 그와 동시에 length를 놓았는데 이아이의 역할은 1번 2번 ... 를갈때마다 길이를 측정하는 것이다. 왜냐하면 우리는 뒤에서부터 2 상태인 아이를 빼주려고 할거니까. 그러려면 몇번째 길이에 도착했을때 화살표를 그 아이에게서 말고 다른 아이로 바꿔줄까를 생각해 주어야 하기때문이다. 그 고민을 밑에 for문이 해주고있다. 뒤에서 몇번째 아이를 빼고싶을때 그때 current는 빼고싶은 아이 앞까지 화살표를 뛰어간다. 그러고나서, 그 도착한 아이의 다음화살표를 current.next.next로 해준다. 그래야 5로 가주지. 그리고나서 head 리턴하면 끝.

문제점이 뭐냐면,
하고싶은것을 표현이 안된다. 새로운 언어 배우고 머리에 뭔가 떠다니는데 말이 안나오는 느낌이다. 자자자. 우선 이것의 또다른 방법이 런너기법이라해갖고, 빨리가는 포인터, 느리게가는 포인터를 사용해서 하는거란다. 그거 우선 연구해보러 가겠다.

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        '''
        Input: head = [1,2,3,4,5], n = 2
        Output: [1,2,3,5]
        '''
 		current = ListNode(0)
        current.next = head
        #dummy > 1 > 2 > 3 > 4 > 5
        slow = fast = current
        
        
        
        for i in range(n):
            fast = fast.next
        
        while fast.next: 
            slow = slow.next 
            fast = fast.next
        
        slow.next = slow.next.next 
        
        return current.next
        

알아냈다 이방법이다. 런너기법이라고한다. 런너기법이란 1)빠르게 가는 아이와 2)느리게 가는 아이 둘을 이용해서 차근차근 리스트를 훑는것이다. 그리고 빠르게 가는 아이 와 느리게 가는 아이의 둘의 간격이 찾고싶은 n만큼 벌려서 이동한다. 간격을 만들어주기위해서는, 우선 head 시작전에 더미노드를 만들어준다. 여기서부터 시작해서 간격을 확장시켜주기위해서 만들어준다고한다. 처음에 내가 시도한건 무조건 처음부터 시작을 하는것이였다. 즉, 1부터 시작하게하는것이였다. 그렇게 풀수도 있지만, 예외처리를 힘들게 많이해줘야하고, 나중에 먼저 간 빠른 아이와 늦게간 아이와의 간격차이를 만들고난후 화살표를 바꿔줘야하는 차례에서 잘못 건너뛰거나 에러가 많이나서...이 방법으로 했다. for문에서 먼저 fast를 간격만큼 벌려주고, while문을 써서 느린아이가 천천히 한칸씩 뒤따라오게, 그리고 아까 for문 간격 멈춘 지점부터 fast아이가 한칸한칸 끝까지 이동하게한후, fast가 끝에 도달했을때, 즉 5에 도달했을때, slow아이가 4를 건너뛰고 5를 가르키도록 slow.next.next해준다.
그리고나서 깔끔하게 current.next 리턴시킨다.

Linkedlist. 이건 사실 쉬워보이고 구현도 쉬워보인다. 하지만, 덜컥 겁을 나게하는 아주 무서운 아이였다. 그래서 오늘 날잡고 이것만했다. 정말 해결책 한번도안보고 오로지 코딩한줄한줄 생각하면서 했다. 무지성으로 코드를 생각없이 갈기는 습관을 최대한 버려야한다. 그래야 논리적으로 코드를 짤수있을것같다.

이상.