[python3] 2130. Maximum Twin Sum of a Linked List

풀이 일자: 23.05.17

난이도: [Medium]

분류: [Linked List, Two Pointers, Stack]

문제 내용

오늘의 문제는 LinkedList가 주어졌을 때 i번째 노드와 n-1-i번째 노드를 twin이라고 했을 때 여러 twin들이 등장할 텐데 이 twin내의 노드값의 합이 최대가 되는 값을 리턴하는 문제이다.

 

문제 해결 흐름

 

1. 가장 간단하게 array에 값을 저장해놓고 값을 확인했다.

class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        arr = list();
        while head:
            arr.append(head.val);
            head = head.next;
        
        ans = 0;
        n = len(arr)
        for i in range(n//2):
            ans = max(ans, arr[i]+arr[n-i-1]);
        
        return ans;

 

Time Complexity:  O(N)

LinkedList내의 노드를 순회해야하기에 N의 시간복잡도를 가지게 된다.

 

Space Complexity: O(N)

해당 노드에 해당하는 만큼의 배열의 크기가 생겨날 것이기에 N의 공간복잡도를 가지게 된다.

 

 

다른 해결 방식

1. 좀더 빠른 방법에 대해 찾아보았다. ( Official Solution)

→ 일반적인 아이디어는 저번에 토끼와 거북이 알고리즘을 통해 그래프에 Cycle이 있음을 확인한 적이 있다. 그때 2개의 포인터를 사용하여 하나의 포인터는 다른 하나의 포인터보다 2배의 속도로 이동했다.

→ 이를 통해 중간 지점을 찾고 해당 중간 지점 이후부터의 LinkedList를 반대로 뒤집는다면 실질적으로는 N/2정도의 시간복잡도를 가지며 줄어들 것이다.

class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        slow, fast = head, head
        ans = 0;

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        
        curr, prev = slow, None;
        while curr:
            curr.next, prev, curr = prev, curr, curr.next

        start = head
        while prev:
            ans = max(ans, start.val + prev.val)
            prev = prev.next
            start = start.next
        
        return ans;

 

Time Complexity:  O(N)

Node의 갯수인 N개의 반정도의 순회를 돌기 때문에 시간복잡도는 N이라고 볼 수 있다.

 

Space Complexity: O(1)

어떠한 자료구조를 사용하지 않고 기존의 LinkedList를 변형해서 풀었기 때문에 1의 시간복잡도를 가진다.

 

 

문제 링크

https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/description/

Maximum Twin Sum of a Linked List - LeetCode