1071. Greatest Common Divisor of Strings

#Easy

For two strings s and t, we say "t divides s" if and only if s = t + ... + t (i.e., t is concatenated with itself one or more times).

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

Constraints:

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of English uppercase letters.

Solv

from math import gcd
class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 + str2 != str2 + str1:
            return ""
        return str1[:gcd(len(str1),len(str2))]

math.gcd

math — 수학 함수

이 모듈은 C 표준에서 정의된 수학 함수에 대한 액세스를 제공합니다. 이 함수는 복소수와 함께 사용할 수 없습니다; 복소수를 지원해야 하면 cmath 모듈에 있는 같은 이름의 함수를 사용하십시오. 대부분 사용자는 복소수를 이해하는 데 필요한 수준의 수학을 배우고 싶어 하지 않기 때문에 복소수를 지원하는 함수와 그렇지 않은 함수를 구별했습니다. 복소수…

Python documentation

지정된 정수 인자의 최대 공약수(greatest common divisor)를 반환합니다. 인자 중 하나가 0이 아니면, 반환된 값은 모든 인자를 나누는 가장 큰 양의 정수입니다. 모든 인자가 0이면, 반환 값은 0입니다. 인자가 없는 gcd()는 0을 반환합니다.

최대공약수는 두 수를 나눌 수 있는 가장 큰 정수를 의미한다. 받는 변수도 정수이어야 하는데 도무지 string에 어떻게 활용할 지가 의문일 수가 있다. 위의 코드에서는 특정한 해당 경우이기 때문에 사용 가능하다.

두 문자열의 공통 부분 문자열을 찾는 문제이다. 이 문제는 문자열을 숫자의 최대공약수 계산과 연결시키는 흥미로운 예시이다. 두 문자열의 가장 긴 공통 부분 문자열을 찾아 반환한다. 이를 위해 최대공약수 개념을 사용한다.

우선 두 문자열끼리 앞 뒤로 연결해서 동일한지 확인한다. 이것은 두 문자열이 같은 패턴의 반복으로 구성되어 있는지를 검사한다. 이 조건을 만족하지 않으면, 공통부분 문자열이 존재하지 않으므로 빈 문자열을 반환한다. 마치 모든 인자가 0일 경우 반환값이 0인 것과 같다.

이후 gcd를 제대로 활용한다. str1[:gcd(len(str1), len(str2))] 이렇게 해줄 경우 str1에서 필요한 부분만 취하는 것이데, 그 부분은 str1, str2의 길이 두 개의 공통부분만큼만을 찾아가는 것이다. 이미 위에서 공통되는 부분이 없는 것은 쳐냈기 때문에 이러한 과정만 해주면 되는 것이다. 이것을 통해서 문자열인데 마치 숫자의 최대공약수를 구하는 것과 같아진다.

Gcd without math.gcd

1. Euclidean Algorithm

만약 python처럼 built-in math.gcd가 없는 경우에는 어떻게 해야할까? 이러한 경우는 유클리드 알고리즘을 사용한다. 이 알고리즘은 두 수의 최대공약수를 효율적으로 찾는 방법으로 알려져 있다.

def gcd(a,b):
  while b != 0:
    a,b = b, a%b
  return a

이 코드에서는 a%b 연산을 통해 나머지를 구하고, a, b 를 업데이트하여 최대공약수를 찾는다. b가 0이 될 때까지 이 과정을 반복하며, b가 0이 되면 현재의 a가 최대공약수가 되는 방식이다.

2. Recursive Euclidean Algorithm

def gcd_recursive(a,b):
  if b == 0:
    return a
  else:
    return gcd_recursive(b, a%b)

재귀적 방식은 같은 원리로 작동하지만, 반복문 대신 재귀 호출을 사용하여 최대공약수를 구한다.