[LeetCode] 2709. Greatest Common Divisor Traversal

👨‍💻 개인 공부 기록용 블로그 입니다.
💡 틀린 내용이나 오타는 댓글, 메일로 제보해주시면 감사하겠습니다!! (__)

링크

https://leetcode.com/problems/greatest-common-divisor-traversal/description/?envType=daily-question&envId=2024-02-25

문제

You are given a 0-indexed integer array nums, and you are allowed to traverse between its indices. You can traverse between index i and index j, i != j, if and only if gcd(nums[i], nums[j]) > 1, where gcd is the greatest common divisor.

Your task is to determine if for every pair of indices i and j in nums, where i < j, there exists a sequence of traversals that can take us from i to j.

Return true if it is possible to traverse between all such pairs of indices, or false otherwise.

 

Example 1:

Input: nums = [2,3,6]
Output: true
Explanation: In this example, there are 3 possible pairs of indices: (0, 1), (0, 2), and (1, 2).
To go from index 0 to index 1, we can use the sequence of traversals 0 -> 2 -> 1, where we move from index 0 to index 2 because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1, and then move from index 2 to index 1 because gcd(nums[2], nums[1]) = gcd(6, 3) = 3 > 1.
To go from index 0 to index 2, we can just go directly because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1. Likewise, to go from index 1 to index 2, we can just go directly because gcd(nums[1], nums[2]) = gcd(3, 6) = 3 > 1.

Example 2:

Input: nums = [3,9,5]
Output: false
Explanation: No sequence of traversals can take us from index 0 to index 2 in this example. So, we return false.

Example 3:

Input: nums = [4,3,12,8]
Output: true
Explanation: There are 6 possible pairs of indices to traverse between: (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), and (2, 3). A valid sequence of traversals exists for each pair, so we return true.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

문제 설명 및 요점

• 10만 이하의 양수로 이루어진 배열이 주어진다.
• 페어에 대해 최대공약수가 1 이상이라면, 두 숫자끼리 순회가 가능한 것으로 취급한다.
• 주어진 배열에 있는 모든 숫자를 순회 가능한지 여부를 체크한다.

풀이

#수학 #유클리드호제법 #그래프 #Union-find #BFS

• 엣지 케이스가 꽤 있어 화나는 문제. -> [1, 1]은 False인데, [1]은 True 이다.
• 처음에는 각 페어 별로 GCD(최대 공약수)를 모두 구해보는 방식으로 구현했다.
  • GCD가 1 이상이면, Union-find 를 통해 같은 컴포넌트로 연결시켜주었다.
  • 일단 각 페어를 모두 계산해보는게 \( O(N^2) \) 이고, Union-find에도 추가 비용이 발생하므로 시간초과.
• 도저히 줄일 방법이 생각이 안나서, 힌트를 모두 열어 참고했다.
  1. 각 인덱스에 대해 소인수 리스트 작성
  2. 소인수 리스트에 대해 이웃끼리 엣지 생성. 순서는 중요치 않음. 모든 페어의 엣지를 검사하기 보다는, 두 이웃간 엣지만 있으면 된다.
  3. 이제 이 문제는 모든 숫자(그래프의 노드)가 동일한 연결된 컴포넌트에 있는지 확인하는 것과 유사함.
  4. 연결된 컴포넌트를 찾는 알고리즘 (BFS, DFS, Union-find 등) 은 모두 유효함
• ‘그래프 문제로 모델링 할 수 있는가?’ 가 핵심인 문제 같다.
  • ‘순회 가능한지’ 체크하는 부분에서 연결된 컴포넌트 찾기를 떠올렸어야 한다.
  • 하지만 모든 경우의 수에 대해 일일이 GCD를 계산해보며 이을 것인가?
• 각 숫자를 한 번씩만 보고도 정답을 구할 수 있다.
  • 어떤 숫자를 소인수 분해 했을 때, 지수를 제외한 밑의 리스트를 인수 리스트라고 하자.
  • 인수 리스트에 속하는 숫자끼리는 이을 수 있다.
  • 만약 [2, 3, 6]이 존재하고 6을 소인수 분해 하여 [2, 3]을 얻은 상황이라면, 2와 3을 이을 수 있게 되는 것이다.
  • 인수로 2를 가지는 어떤 숫자와 3을 가지는 어떤 숫자는 현재 숫자를 중간 노드로 두고 방문할 수 있다는 뜻이 된다.
  • 모든 숫자에 대해 인수 리스트 를 구하여 그래프를 생성했다면, 이 그래프가 하나의 컴포넌트인지 검사하면 된다.
• 원리를 알아도 구현하기 쉽지 않았다.
  • 크게 “1. 특정 숫자를 소인수분해 하여 인수 리스트 를 구하고, 그래프로 모델링하기” 와 “2. 그래프가 하나의 컴포넌트로 존재하는지 검사하기” 파트로 나누었다.
  • 기본적인 소인수분해 알고리즘을 통해 인수 리스트를 구하였다. 3부터는 2씩 점프해도 되고, 초기 숫자의 제곱근 만큼만 돌아도 된다.
  • 다만 제곱근 만큼만 돈다면, 마지막 연산 결과가 2 이상인지 꼭 체크해봐야 한다. 1이 아니라면 마지막 소인수가 된다.
  • 이를 set을 통해 그래프로 모델링해주었다.
  • 인수 리스트에 속하는 모든 숫자에 대해 인수 리스트 - {숫자} 를 하면, set이기 때문에 특정 숫자만 빠진 집합을 얻을 수 있다.
  • 이를 defaultdict(set)에 존재하는 기존 집합과의 합집합 연산을 통해 합친다.
  • 최종적으로, key는 소인수 중 하나, value는 해당 소인수와 이어진 다른 소인수의 set이 된다.
  • 이렇게 구한 그래프는 여러 방법을 통해 하나의 컴포넌트로 연결되었는지 검사할 수 있다. 난 BFS를 사용하였다.
  • key의 맨 처음 값을 가져와서 해당 값으로 BFS를 1회 수행하고, 방문하지 않는 다른 노드가 있다면 False를, 없다면 True를 반환하였다.
  • 방문한 노드를 저장하는 set과 기존 key와의 교집합을 구했을 때 기존 key가 그대로 나오는 지 검사하면 된다.
• 풀고 나니 구현이 더 간단한 풀이법이 존재했다. 아마 파이썬만 가능할 것으로 보인다.
  • 주어진 숫자를 중복 제거 후 내림차순 정렬한다.
  • 기본적으로 각 페어의 GCD를 검사할 것이다. 하지만 검사 횟수를 확 줄일 수 있다.
  • 하나의 기준점(i)을 잡고, 해당 숫자의 오른쪽(j: i+1 ... N)만 본다.
    • 두 숫자의 GCD를 게산하여 1보다 크다면, “기준점에 있던 숫자(nums[i])를 GCD로 나눈 값”을 페어를 이루는 숫자(nums[j])에 곱하여 저장한다.
    • 이는 인수를 뒷 숫자에 쌓아버리는 효과가 있다. (수가 굉장히 커질 수 있지만, 인수 리스트 를 이어 그래프를 생성하는 것과 같은 효과이다.)
    • 다음 기준점(i++)으로 이동한다.
  • j가 끝까지 돌았는데도 i에 있는 숫자를 쌓을 수 없다면, 이 숫자는 어떠한 숫자와도 연결할 수 없다는 뜻이 되므로 바로 False를 리턴할 수 있다.

코드

from collections import defaultdict
from collections import deque

class Solution:
    def getPrimeFactorEdges(self, primeFactorList: dict[set], num: int) -> None:
        factor = set()
        origin = num
        while num % 2 == 0:
            factor.add(2)
            num //= 2
        
        for i in range(3, int(origin ** 0.5) + 2, 2):
            while num % i == 0:
                factor.add(i)
                num //= i

        if num >= 2:
            factor.add(num)

        for f in factor:
            primeFactorList[f] |= factor - {f}

    def isAllConnected(self, primeFactorList: dict[set]) -> bool:
        visited = set()
        start = list(primeFactorList.keys())[0]
        q = deque([start])
        visited.add(start)
        while q:
            prev = q.popleft()
            for curr in primeFactorList[prev]:
                if curr not in visited:
                    visited.add(curr)
                    q.append(curr)

        return visited & primeFactorList.keys() == primeFactorList.keys()


    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True
        if 1 in set(nums):
            return False

        primeFactorList = defaultdict(set)
        
        for num in nums:
            self.getPrimeFactorEdges(primeFactorList, num)

        return self.isAllConnected(primeFactorList)

from math import gcd

class Solution:
    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        if 1 in nums and len(nums) > 1: return False

        nums = sorted(list(set(nums)), reverse=True)

        LEN = len(nums)
        for i in range(LEN-1):
            for j in range(i+1, LEN):
                temp = gcd(nums[i], nums[j])
                if 1 < temp:
                    nums[j] *= nums[i] // temp
                    break
            else:
                return False
        return True