[Leetcode]2807. Insert Greatest Common Divisors in Linked List

문제 요약

• 알고리즘 분류:Linked List, 유클리드호제법
• 난이도: Medium
• 문제내용:
  • 연결 리스트의 헤드 head가 주어지며, 각 노드는 정수 값을 포함하고 있습니다.
  • 인접한 모든 노드 쌍 사이에, 두 노드의 최대공약수와 같은 값을 가진 새로운 노드를 삽입하세요.
• 사이트 주소: https://leetcode.com/problems/insert-greatest-common-divisors-in-linked-list/description/

문제풀이

 이번 문제는 링크드 리스트에 중간에 최대 공약수를 집어 넣는것이다. 최대 공약수 효율적으로 구하는 방법은 유클리드 호제법이다. 유클리드 호제법에 대한 설명은 아래 글에서 확인해보면된다.

https://jih3508.tistory.com/13

유클리드 호제법(Euclidean algorithm)

접근 방법

1. 최대공약수(GCD) 계산

최대공약수를 계산하는 가장 효율적인 방법은 유클리드 알고리즘을 사용하는 것입니다. 유클리드 알고리즘은 다음과 같은 성질을 이용합니다:

 

GCD(a, b) = GCD(b, a % b) (a % b ≠ 0인 경우)
GCD(a, 0) = a

이를 이용하여 재귀적으로 또는 반복문을 통해 최대공약수를 계산할 수 있습니다.

2. 연결 리스트 순회 및 노드 삽입

연결 리스트를 순회하면서 각 노드와 다음 노드의 값으로 최대공약수를 계산하고, 이 값을 가진 새 노드를 두 노드 사이에 삽입합니다.

 

마무리

이 문제는 연결 리스트와 최대공약수라는 두 가지 기본적인 컴퓨터 과학 개념을 결합한 흥미로운 문제입니다. 유클리드 알고리즘을 사용하여 효율적으로 최대공약수를 계산하고, 연결 리스트를 순회하면서 필요한 노드를 삽입하는 방법을 배울 수 있었습니다.

 

Code

Python

class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:

        # 두 정수의 최대공약수를 계산하는 함수
        def GCD(x, y):
            while y != 0 and x % y != 0:
                r = x % y
                x, y = y, r

            return y

        node = head # 현재 처리 중인 노드

        while node.next is not None: # 다음 노드가 있는 동안 반복

            next_node = node.next # 다음 노드 참조 저장

            gcd = GCD(node.val, next_node.val) # 현재 노드와 다음 노드 값의 최대공약수 계산
            new_node = ListNode(gcd) # 최대공약수 값을 가진 새 노드 생성

            # 새 노드를 현재 노드와 다음 노드 사이에 삽입
            new_node.next = next_node # 현재 노드가 새 노드를 가리키도록 함
            node.next = new_node # 새 노드가 다음 노드를 가리키도록 함

            node = next_node # 처리할 노드를 다음 노드로 이동


        return head

Java

class Solution {

    // 최대 공약수 구하는 함수
    public int GCD(int x, int y) {
        while(x % y != 0){
            int r = x % y;
            x = y;
            y = r;
        }
        return y;
    }

    public ListNode insertGreatestCommonDivisors(ListNode head) {

        ListNode node = head;  // 현재 처리 중인 노드

        while (node.next != null) {  // 다음 노드가 있는 동안 반복
            ListNode nextNode = node.next;  // 다음 노드 참조 저장

            int val = GCD(node.val, nextNode.val);  // 현재 노드와 다음 노드 값의 최대공약수 계산
            ListNode newNode = new ListNode(val);   // 최대공약수 값을 가진 새 노드 생성

            // 새 노드를 현재 노드와 다음 노드 사이에 삽입
            node.next = newNode;     // 현재 노드가 새 노드를 가리키도록 함
            newNode.next = nextNode; // 새 노드가 다음 노드를 가리키도록 함

            node = nextNode;  // 처리할 노드를 다음 노드로 이동
        }

        return head;
    }
}

Javascript

var insertGreatestCommonDivisors = function(head) {
    // 두 정수의 최대공약수를 계산하는 함수
    const GCD = (x, y) =>{
        while(y != 0 && x % y != 0){
            const r = x % y;
            x = y;
            y = r;
        }
        return y;
    }

    let node = head; // 현재 처리 중인 노드

    while(node.next != null){ // 다음 노드가 있는 동안 반복
        const nextNode = node.next; // 다음 노드 참조 저장

        const gdc = GCD(node.val, nextNode.val); // 현재 노드와 다음 노드 값의 최대공약수 계산
        const newNode = new ListNode(gdc);  // 최대공약수 값을 가진 새 노드 생성


        // 새 노드를 현재 노드와 다음 노드 사이에 삽입
        node.next = newNode;     // 현재 노드가 새 노드를 가리키도록 함
        newNode.next = nextNode; // 새 노드가 다음 노드를 가리키도록 함

        node = nextNode;  // 처리할 노드를 다음 노드로 이동
    }
    
    return head;
};