2130. Maximum Twin Sum of a Linked List

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

 

문제

n이 짝수인 크기의 링크된 목록에서 0 <= i <= (n / 2) - 1이면 링크된 리스트의 n번째 노드(0-indexed)를 (n-1-i)번째 노드의 쌍둥이 노드라고 합니다.
예를 들어 n = 4인 경우 노드 0은 노드 3의 쌍둥이이고 노드 1은 노드 2의 쌍둥이입니다. 이들은 n = 4에 대해 쌍둥이를 가진 유일한 노드입니다. 쌍둥이 합은 노드와 그 쌍둥이의 합으로 정의됩니다.
길이가 짝수인 연결된 목록의 헤드가 주어지면, 연결된 목록의 최대 쌍둥이 합을 반환합니다.

 

풀이

기본적인 풀이 접근 방식은 다음과 같다. twin의 합을 구하는 가장 쉬운 방법은 가장 처음 시작 인덱스와 가장 마지막 인덱스가 twin 관계이기 때문에 이 두 지점부터 시작하여, 점점 한 칸씩 이동해서 합을 구하고 가장 큰 합을 도출하는 방법이다.

문제는 노드들이 링크드리스트이기 때문에 이러한 접근 방식을 적용하기 위해서는 별도의 작업이 필요하다는 점이다.

먼저 링크드리스트를 절반으로 나누고 절반으로 나눠진 링크드리스트의 후반부를 reverse하여 초반의 링크드 리스트와 후반의 링크드 리스트를 순회하며 합을 구하는 방법이다.

 

1. 링크드 리스트를 절반으로 나누기

주어진 링크드 리스트의 길이가 얼마인지 알 수도 없고, 중간 지점 또한 모른다. 따라서 O(n)의 시간복잡도와 추가적인 공간복잡도를 발생시키지 않는 선에서 링크드 리스트를 정확히 절반으로 나누기 위해 투포인터에서 '토끼와 거북이' 알고리즘을 활용했다.

일반적으로 링크드 리스트에서 '사이클'이 발생하는지 확인하기 위해 사용하지만, 이번 풀이에서는 링크드리스트를 절반으로 나누기 위해 활용했다.

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

slow와 fast 2개로 나누어서 slow가 한 칸 움직일 동안 fast는 2칸씩 움직이는 방법이다. fast 포인터가 끝까지 도달하는 순간 slow는 링크드 리스트를 절반으로 나누는 지점에 도달하게 된다.

예를 들어  (0-indexed 일때) 
n이 4일때 fast 포인터는 인덱스 3에서 멈추게 되고 slow 포인터는 2에서 멈추게 된다. - 예시의 3
(1 - 2 - 3 - 4 )

n이 6일때 fast 포인터는 인덱스 5에서 멈추게 되고 slow 포인터는 3에서 멈추게 된다. - 예시의 4

(1 - 2 - 3 - 4 - 5 - 6)

n이 8일때 fast 포인터는 인덱스 6에서 멈추게 되고 slow 포인터는 4에서 멈추게 된다. - 예시의 5

(1 - 2 - 3 - 4 - 5 - 6 - 7 - 8)

이렇듯 해당 알고리즘은 slow 포인터가 링크드 리스트를 정확히 절반으로 나눠지는 부분을 찾는 것을 보장한다.

 

2. 절반으로 나눈 링크드리스트를 반전시킨다.

앞서 말한대로 twin 관계의 합을 구하는 방식은 인덱스의 처음과 끝부터 시작해서 점차 포인터를 각각 한 칸씩 이동시키면서 합을 구하면 된다. 하지만 제시된 링크드 리스트의 특성상 노드의 다음 노드를 확인할 수는 있어도 이전 노드를 확인할 수는 없다. 이를 위해서 나눠진 링크드 리스트의 second를 반전시킨다.

prev = None
while slow:
    next_node = slow.next
    slow.next = prev
    prev = slow
    slow = next_node

 

slow는 나눠진 링크드 리스트의 second가 된다. 주어진 링크드 리스트는 다음 노드의 값만 알고 있는 싱글 링크드 리스트이다. 따라서 가장 마지막 노드의 다음 노드는 None이 된다. 이러한 특성을 이용하여 노드를 재배치하는 방식으로 문제를 풀 수 있다.

예를 들어 

1 - 2 - 3 - 4 의 형식으로 노드가 있다고 가정해보자. 싱글 링크드 리스트의 방식에서 반전 시키는 방식은 새로운 링크드 리스트를 재구성하는 것이다. 

이때 필요한 것은 prev 와 next라는 2개의 포인터가 필요하게 된다. prev는 이전 노드들이다. next는 다음 노드들이다.

현재 노드의 다음 노드를 이전 노드로 교체한다. 현재 노드를 이전 노드로 교체한다. 그리고 다음 노드가 현재 노드가 된다. 

1 - 2 - 3 - 4 의 형식으로 구성되어 있다고 할 때, 2 - 3 - 4 의 노드들은 next_node에 저장된다. 그리고 1 노드의 다음 노드는 None가 되게 된다.

그러면 slow 노드는 1 - None이 되고 / next_node는 2 - 3 - 4가 된다. 이제 slow 노드는 prev 노드에 저장하고 next_node는 slow 노드에 저장한다. 이렇게 slow 노드가 None이 될 때까지 반복해주면, prev노드에는 slow노드들이 역순으로 정렬되어 있게 될 것이다.

 

3. 순회하면서 최대 합을 구하기

이제 이 노드들을 함께 순회하면서 최대 합을 갱신해주면 된다.

maxV = 0
while prev:
    sumV = head.val + prev.val
    maxV = max(sumV, maxV)
    head = head.next
    prev = prev.next

return maxV

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        slow = fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        prev = None
        while slow:
            next_node = slow.next
            slow.next = prev
            prev = slow
            slow = next_node

        maxV = 0
        while prev:
            sumV = head.val + prev.val
            maxV = max(sumV, maxV)
            head = head.next
            prev = prev.next

        return maxV