[파이썬/Python] Leet Code 1071(Easy): Greatest Common Divisor of Strings

숨·2025년 8월 30일

코테

알고리즘 문제 풀이

목록 보기

124/128

📌 문제 : Leet Code 1071

📌 문제 탐색하기

str1, str2 : 입력되는 2개의 문자열 ( $1 ≤ tr1.length, str2.length ≤ 1000$ )

문제 풀이

2개의 문자열 s, t가 있을 때, s은 여러 개의 t로 나눠질 수 있다. (t가 1개 일수도 더 많을 수도 있다)
이 때, str1, str2가 주어졌을 때 str1, str2 둘다를 나눌 수 있는 가장 긴 x를 찾는 문제이다.

x는 str1, str2를 모두 나눌 수 있는 문자열이라는 것은 x를 반복하면 str1, str2 모두 만들 수 있다는 의미이다.
따라서 이 두 문자열 길이에 x 길이를 나누었을 때 나누어 떨어져야 하므로 두 문자열 길이의 최대 공약수가 될 수 있는 x의 최대 길이라 할 수 있다.

최대 공약수의 길이를 구하고 str1의 첫번째 인덱스부터 최대공약수 길이만큼 슬라이싱하고,
이 슬라이싱한 문자열을 반복했을 때 str1, str2 모두를 만들어낼 수 있는지 확인해서 결과값을 반환하면 될 것이다.

가능한 시간복잡도

나누어 떨어지는지 확인하는 함수 → $O(len(str1) + len(str2))$
최대공약수 계산 → $O(log(min(len(str1), len(str2))))$

최종 시간복잡도
최악의 경우 $O(len(str1) + len(str2)) = O(2000)$ 이므로 충분히 동작할 수 있다.

알고리즘 선택

나누어 떨어지는지 확인하기

📌 코드 설계하기

s가 t를 반복해 만들어지는지 확인하는 함수
문자열 길이의 최대공약수 구하기
str1 중 길이가 최대공약수인 부분을 후보 설정
반복해서 만들 수 있는지 확인
조건에 따라 결과 반환

📌 시도 회차 수정 사항

1회차

문제를 완전히 잘못 이해해서 LCS(Longest Common Subsequence)라는 최장 문자열 길이 찾기 방식으로 풀려고 했다. 문제에서 분명히 s는 t로 나눌 수 있는 문자열이라고 했는데 그냥 맘대로 str1, str2의 공통 문자열 중에 가장 긴 것을 찾으면 된다고 생각한 것이다.
문자열의 최대 공약수를 구하는 문제라는 것을 후에 알아차리고 다시 풀었다.

📌 정답 코드

import math

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # s가 t를 반복해 만들어지는지 확인하는 함수
        def divides(s, t):
            # 나누어 떨어지지 않으면 t 반복해서 만들기 불가능
            if len(s) % len(t) != 0:
                return False
            # t를 s길이에서 t길이를 나눈 몫만큼 반복한 문자열이 s면 True, 아님 False
            return s == t * (len(s) // len(t))

        # 문자열 길이의 최대공약수 구하기
        gcd_len = math.gcd(len(str1), len(str2))

        # str1 중 길이가 최대공약수인 부분을 후보 설정
        candidate = str1[:gcd_len]

        # 반복해서 만들 수 있는지 확인
        if divides(str1, candidate) and divides(str2, candidate):
            # 되면 최대공약수 문자열 맞음
            return candidate
        else:
            # 아니면 빈 문자열
            return ""

결과

👍 다른 풀이

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
    	# 두 문자열 길이 저장
        len1, len2 = len(str1), len(str2)
		
        # 후보 길이 l이 str1, str2 길이를 모두 나누는지 확인
        def isdivisor(l):
        	# 나누어 떨어지지 않으면 후보 문자열 불가능
            if(len1 % l or len2 % l):
                return False
                
            # 나누어 떨어지면 몇번 반복되는지 계산
            f1,f2 = len1//l, len2//l
            # str1에서 l길이 만큼만 접근한 값에 각각의 몫을 곱해서 두 문자열이 만들어지는지 확인
            return str1[:l] * f1 == str1 and str1[:l] * f2 == str2
        
        # 후보 길이를 l부터 0까지 역방향 탐색 = 길이 긴 것부터 확인
        for i in range(min(len1,len2),0,-1):
        	# 후보가 두 문자열 모두 잘 나누면 해당 문자열 반환
            if(isdivisor(i)):
                return str1[:i]
                
        # 조건 맞는 후보 없으면 빈 문자열 반환
        return ""