알고리즘 - 연결 리스트 개념 + 병합 문제

연결리스트

연결리스트란 고구마 줄기처럼 각 자료들이 연결되어 있는 형태를 말한다.
그냥 배열같은거 아닌가? 라는 생각이 들지만 서로의 특징이 다르다.

배열

1. index로 특정 위치의 자료 접근이 용이하다.
2. 삽입이 어렵다. pop(0)을 하게되면 그 뒤의 자료들이 앞으로 한 칸씩 shift하게 되는 시간복잡이 발생한다.

연결리스트

1. 직접 구현해야함,
2. 탐색이 어려움. 특정 자료를 찾기 위해선 맨 처음부터 줄줄이 찾아들어감
3. 삽입이 쉽다. 원하는 위치로 들어가서 이전 데이터가 삽입할 데이터를, 삽입할 데이터는 이 다음 데이터를 바라보게만 하면 되기 때문

하나의 데이터가 다음 데이터를 바라보게 하는 식으로 데이터간의 결합이 느슨하기 때문에
탐색과 정렬은 배열 리스트, 추가와 삭제가 많이 필요하면 연결리스트를 채용한다

연결리스트 병합

서로 다른 두개의 리스트를 오름차순으로 정렬시키는 문제이다.
아래는 처음에 접근한 방식이다.

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
     
        c1 = list1
        c2 = list2
        answer = dummy = ListNode()
        before = ListNode()
        
        if c1 is None and c2 is None :
            return c1
        elif c1 is None and c2 is not None:
            return c2
        elif c2 is None and c1 is not None:
            return c1
        
        while c1 is not None and c2 is not None :
            if c1.val <= c2.val :
                dummy.val = c1.val
                c1 = c1.next
            else :
                dummy.val = c2.val
                c2 = c2.next
                
            dummy.next = ListNode()
            dummy = dummy.next
                   
        if c1 is None :
            dummy.val = c2.val
            dummy.next = c2.next
        else :
            dummy.val = c1.val
            dummy.next = c1.next
        
        return answer

사실 여기까지 하는 것도 다른 분의 도움을 받아서 완성했다...😂
빈 리스트를 선언해서 더 작은 수를 찾는 조건문을 통해 값을 넣어주고 다음 노드로 넘어가는 로직이다.
여기서 나는 원리는 이해해도 return을 어떻게 시켜야할지 애를 먹은 상황이었다.
dummy를 조작하고 있었으니 return dummy를 해야 맞는게 아닌가? 어떻게 answer에서 전체가 담기지?
내가 파이썬 언어 자체를 잘못 이해하고 있던 것인가?

이는 내가 배열처럼 생각을 하다보니 발생한 일로
리스트 노드의 조작은 포인터처럼 생각을 해야한다고 한다.
answer에 담긴 dummy는 next를 통해 해당 리스트를 돌아다니며 조작을 하는 포인터이며
최종적으로는 answer을 return해야 전체가 반환된다.
그리고 제출결과는 다음과 같다.

성공은 했지만 좋은 답은 아닌 것 같다..
이에 대한 해설답안들을 찾아보니 재귀함수와 스위칭으로 풀어낸 것을 확인할 수 있었다

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if (not l1) or (l2 and l1.val > l2.val):
            l1, l2 = l2, l1
        if l1:
            l1.next = self.mergeTwoLists(l1.next, l2)
        return l1

l1의 값이 작을 경우 l1을 진행시키고 그렇지 않을 경우 l2와 서로 스위칭하여 l1에 l2값을 담아
재귀함수로 계속 전진시키는 방식이다.
가장 모범답안이기에 제출 시 굉장히 빠른 속도를 보여준다.

---

후기

연결리스트라는 구조를 처음 접해봤기 때문에 머릿속으로 그려나가는 것에 애를 먹었고
구현에 있어서도 많은 오류를 접했다. 특히 NoneType 에러..😥
어떻게 연결해야할지 원리는 이해했지만 풀이의 재귀함수와 스위칭의 방법은 생각해보지도 못했기 때문에
굉장히 자괴감이 들어 당일엔 거의 죽상이었는데 일요일에 리프레시 하고 난 후 다시 가만히 풀어보니 이해가 되기 시작한다!
또한 나의 안좋은 습관은 문제를 보면 생각을 정리하기전 우선 구현해본다는 것이었는데
이는 알고리즘 문제를 풀 때는 굉장히 안좋은 습관이라는 것을 깨달았다.
일단 구현을 해놓다보면 내가 써놓은 로직에만 집착하다보니 같은 오류를 계속해서 범하는 문제를 겪게 된다.

다음 알고리즘을 풀때는 두가지를 명심해야겠다.

✔ 문제를 보면 접근 방법과 당위성에 대한 것을 고민하며 전체 로직을 그려본 후 맞다고 판단 될 경우 구현을 시작한다.
✔ 도저히 풀리지 않고 이해가 안 간다면 매이지 말고 리프레쉬 후 처음부터 다시 하나하나 짚어보기