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

문제 요약

• 알고리즘 분류: LinkedList
• 난이도: Medium
• 문제내용:
  • 짝수개 n개의 LinkedList개 있다.
  • i 번째 인덱스와 그 맞은편 n - i - 1인덱스가 쌍둥이 노드 이다.
  • twin sum 쌍둥이 노드의 합이다.
  • 쌍둥이 노드의 합중 가장 큰것을 구하여라
• 사이트 주소: https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/

문제풀이 

 이번 문제는 링크드 리스트활용 하는 간단한 문제이다. 구현은 아래와 같이 하면 된다.

1. LinkedList 순회 하면서 List저장 한다.(문제에서는 몇개 노드인지 주어지 않아서 삽입삭제 가능한 자료구조를 사용해야 한다.)
2.  저장한 리스트에서 0 번 부터 N / 2 인덱스까지 탐색하면서 twin sum(i + n - i - 1)을 구하고 그중 큰값을 반환 한다.

이렇게 구현하면 시간 복잡도는 O(N)만큰 나온다.

 

Code

Python

class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        valueList = [] # linkedList 값을 순서대로 담을 list

        # linkedList에서 다음 node 없을때 까지 순환한다.
        while head != None:
            valueList.append(head.val)
            head = head.next # 다음 노드로 이동한다.

        size = len(valueList)
        # i와 맞은편 size - 1 - i 위치와 더해서 큰 값을 저장한다.
        return max([valueList[i] + valueList[size - 1 - i] for i in range(size // 2)])

Java

class Solution {
    public int pairSum(ListNode head) {
        List<Integer> list = new ArrayList<>(); // linkedList 값을 순서대로 담을 list
        
        // linkedList에서 다음 node 없을때 까지 순환한다.
        while(head != null){
            list.add(head.val);
            head = head.next; // 다음 노드로 이동한다.
        }

        int size = list.size();
        int maxValue = 0;
        // i와 맞은편 size - 1 - i 위치와 더해서 큰 값을 저장한다.
        for (int i = 0; i < size / 2; i++) {
            maxValue = Math.max(maxValue, list.get(i) + list.get(size - 1 - i));
        }

        return maxValue;
    }
}