리트코드 - 1071. Greatest Common Divisor of Strings

https://leetcode.com/problems/greatest-common-divisor-of-strings/

Greatest Common Divisor of Strings - LeetCode

해당 문제는 두 개의 문자열이 주어졌을 때, 해당 문자열을 모두 나누는 최대 길이의 문자열을 구하면 된다.

 

예를 들어 "ABAB" 라는 문자열은 "AB"로 반복되기 때문에 해당 문자열은 "AB"로 나뉘어진다고 할 수 있다. ( == divisor)

그러면 문자열은 2개니까 기본적으로 해당 문자열이 공통적으로 나뉘기 위한 조건으로는 두 수에 대한 공약수여야 한다는 점이다.

따라서 입력 문자열 길이의 최대 공약수를 구하고 해당 수부터 반복문을 진행하면서 brute-force하게 common divisor의 여부를 확인하는 방향으로 문제를 풀었다.

from math import gcd
class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        len_one, len_two = len(str1), len(str2)
        gcd_len = gcd(len_one, len_two) # O(log n)
        
        def is_gcd(gcd_len): # O(gcd_len)
            if len_one % gcd_len or len_two % gcd_len:
                return False
            else:
                l1, l2 = len_one // gcd_len, len_two // gcd_len
                base = str1[:gcd_len] # O(gcd_len) 슬라이싱의 시간 복잡도는 슬라이싱의 길이에 비례
                return str1 == l1 * base and str2 == l2 * base

        for i in range(gcd_len, 0, -1): # O(gcd_len)
            if is_gcd(i):
                return str1[:i] # O(i) 최악의 경우 O(gcd_len)
            return ""

 

처음에 각 문자열들의 길이의 최대 공약수를 구한다. gcd의 시간복잡도는 유클리드 호제법을 사용하기 때문에 시간복잡도는 O(log n)이다.

이후 gcd_len 부터 역으로 for 루프를 순회하면서 is_gcd 함수를 호출한다. is_gcd 함수는 각 문자열에 대한 common divisor의 여부를 확인하고 그렇지 않을 경우 false를 반환한다.

 

이렇게 gcd_len 만큼 2번 순회하기 때문에 시간 복잡도는 O(n^2)이다.

 

다른 풀이

str1과 str2가 문자열 x의 반복으로 구성된다면, x는 str1과 str2의 최대공약수가 될 것이라는 관점의 풀이이다.

이는 x의 길이가 str1과 str2의 길이를 나누어 떨어져야 한다는 것을 의미하며, 이는 수의 최대공약수 정의와 일치한다.

from math import gcd

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
    
        gcd_len = gcd(len(str1), len(str2)) # O(log(min(len(str1), len(str2))))
        
        base = str1[:gcd_len] # O(log(min(len(str1), len(str2))))
        
        if str1 == base * (len(str1) // gcd_len) and str2 == base * (len(str2) // gcd_len): 
			# O(len(str1)) + O(len(str2))
            return base 
        
        return ""

 

gcd 함수는 O(log(min(len(str1), len(str2)))) 시간이 걸린다. 

 

문자열 비교 연산(==): 두 문자열이 동일한지 비교하는 데에는 두 문자열의 길이에 비례하는 시간이 소요된다. 따라서 각 비교 연산의 시간 복잡도는 각각 O(len(str1))와 O(len(str2))이다.

 

따라서, 전체 코드의 시간 복잡도는 O(len(str1) + len(str2))이다.