3 분 소요

Divide Conquer

문제

문제 링크

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

Input: head = [4,2,1,3] Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0] Output: [-1,0,3,4,5]

Example 3:

Input: head = [] Output: []

Constraints:

  • The number of nodes in the list is in the range [0, 5 * 104].
  • -105 <= Node.val <= 105

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

스스로 고민

접근법

  • 링크드 리스트에 연결되어 있는 값들을 오름차순으로 정렬하기

의사코드

  • 반복문으로 head에 있는 값들은 전부 뽑아냄
  • 뽑아낸 값들을 리스트에 넣어줌
  • 리스트를 정렬
  • 정렬한 리스트 순서대로 다시 링크드 리스트에 넣어줌

구현 코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        list_nums = []
        while head != None:
            list_nums.append(head.val)
            head = head.next
        list_nums.sort()
        
        right_list = ListNode(0)
        result = right_list
        
        for num in list_nums:
            right_list.next = ListNode(num)
            right_list = right_list.next

        return result.next

시간 복잡도와 공간 복잡도

시간 복잡도:

  1. 연결 리스트를 반복하여 각 노드의 값을 추출하고 리스트에 추가하는 부분은 O(n) 시간이 걸린다. 여기서 ‘n’은 연결 리스트의 노드 수다.
  2. 리스트를 정렬하는 부분은 리스트의 길이가 ‘n’일 때 O(nlogn) 시간이 걸린다.
  3. 정렬된 리스트를 다시 연결 리스트로 변환하는 부분은 O(n) 시간이 걸린다.

따라서 전체 시간 복잡도는 O(n) + O(nlogn) + O(n) = O(nlogn) 다.

공간 복잡도:

  1. 리스트를 저장하기 위한 list_nums 리스트가 필요하며, 이 리스트의 크기는 입력 연결 리스트의 노드 수와 같다. 따라서 공간 복잡도는 O(n) 다.
  2. 정렬을 위해 list_nums를 사용하는 것 이외에 추가적인 공간이 필요하지 않으므로 공간 복잡도는 O(n) 다.

총 공간 복잡도는 O(n) 다.

회고 과정

  • 솔직히 링크드리스트에 대해서 제대로 이해를 못 한거 같다.
  • 이해가 잘 안가는 부분은 프린트로 찍어가면서 이해를 했지만 링크드 리스트 같은 경우 메모리 경로가 나오기 때문에 뭔가 확실한 이해가 잘 안갔다.
        list_nums.sort()

        right_list = ListNode(0)

        result = right_list

        for num in list_nums:

            right_list.next = ListNode(num)

            right_list = right_list.next

        return right_list.next
  • 위와 같이 하면 반환되는 값이 없다.
  • right_list.next 나 result.next나 똑같은거 아닌가 했는데 이 부분이 진짜 이해가 안간다…
  • 이해가 갔다!
  • result를 새로 선언하는게 이해가 안갔는데 result랑 right_list는 같은 메모리를 참조하고 있다. 그래서 right_list에 순서대로 값을 넣어두면 마지막은 none이 되어있다. 하지만 result는 처음 그대로인 상태이고 첫 값은 0이기 때문에 next를 반환하면 이제 순서대로 값이 나온다.

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        add = []
        newhead = head
        while head:
            add.append(head.val)
            head = head.next
        add = sorted(add)
        print(add)
        neww = newhead
        for i in add:
            newhead.val = i
            newhead = newhead.next
        return neww
  • 다른 사람들의 코드를 보고 이제 링크드 리스트 값이 어떻게 진행되어가는지 좀 더 이해가 잘 되었다.
  • 근데 좀 궁금한게 실제로 이렇게 자료구조를 갖는게 DB랑 무슨 상관인지 잘 모르겠어서 좀 찾아 보았다.
  • 좀 찾아보니까 실질적으로 DB랑은 상관이 없고 View나 비즈니스 로직에서 사용된다고 한다. 또한 페이지네이션 같은 경우 데이터 베이스 쿼리 결과를 나누고 각 페이지의데이터를 링크드 리스트나 리스트 형태로 표시를 한다고 한다.
  • 좀 정리하자면 데이터베이스와 관련있는 부분은 데이터를 가져올 떄 이를 효율적으로 표시하거나 정리하는 데 나타내기 좋으며 DB도 또 다른 세계가 있어서 공부를 따로 해야된다고 한다.

댓글남기기

참고