LeetCode 1071. Greatest Common Divisor of Strings

🚀 문제: 1071. Greatest Common Divisor of Strings

• 플랫폼: LeetCode

• 번호: 1071

• 제목: Greatest Common Divisor of Strings

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

• 난이도: Easy  

📝 문제 설명

두 문자열 str1과 str2가 주어졌을 때, 두 문자열의 문자열 최대공약수(GCD of Strings)를 찾는 문제입니다.

문자열 t가 문자열 s를 나눈다는 것은 s = t + t + ... + t (즉, t가 하나 이상 반복되어 s와 같아짐)와 같이 정의됩니다. 우리는 str1과 str2를 모두 나누는 가장 긴 문자열 x를 찾아야 합니다.

예시 1:

• 입력: str1 = "ABCABC", str2 = "ABC"

• 출력: "ABC"

• 설명: "ABC"는 "ABCABC" ("ABC" + "ABC")를 나누고, "ABC"는 "ABC" ("ABC")를 나눕니다.

예시 2:

• 입력: str1 = "ABABAB", str2 = "ABAB"

• 출력: "AB"

• 설명: "AB"는 "ABABAB" ("AB" + "AB" + "AB")를 나누고, "AB"는 "ABAB" ("AB" + "AB")를 나눕니다.

예시 3:

• 입력: str1 = "LEET", str2 = "CODE"

• 출력: ""

• 설명: 두 문자열을 모두 나누는 공통 문자열이 없습니다.

🤔 풀이 아이디어: 길이의 최대공약수를 기반으로 한 탐색

이 문제는 두 문자열을 공통으로 나누는 가장 긴 부분 문자열을 찾는 것입니다. 제가 생각한 접근 방식은 다음과 같습니다.

1. 길이의 최대공약수(GCD) 활용: 만약 두 문자열 str1과 str2에 공통적으로 반복되는 부분 문자열 X가 존재한다면, str1의 길이는 len(X)의 배수여야 하고, str2의 길이도 len(X)의 배수여야 합니다. 따라서, 가능한 X의 길이 len(X)는 len(str1)과 len(str2)의 공약수여야 합니다. 우리가 찾는 가장 긴 X의 길이는 gcd(len(str1), len(str2))의 약수 중 하나가 될 것입니다.

2. 후보 길이 탐색: 가장 긴 X를 찾아야 하므로, 가능한 길이 중 가장 긴 것부터 확인합니다. gcd(len(str1), len(str2))부터 시작해서 1까지 길이를 줄여가며 각 길이 i에 대해 다음을 확인합니다.

   • 길이 i를 가지는 str1의 접두사(prefix) 또는 str2의 접두사를 후보 문자열 P로 설정합니다. (예: str1[:i] 또는 str2[:i])

   • str1이 이 후보 문자열 P를 반복하여 구성되는지 확인합니다. (즉, str1 == P * (len(str1) // i))

   • str2도 이 후보 문자열 P를 반복하여 구성되는지 확인합니다. (즉, str2 == P * (len(str2) // i))

   • 두 조건이 모두 만족되면, 해당 P가 현재까지 찾은 가장 긴 공통 divisor이므로 반환합니다.

3. 특별 케이스 처리:

   • 만약 str1과 str2의 길이가 같다면, 두 문자열이 완전히 동일해야 그 문자열 자체가 GCD가 되고, 다르면 공통 divisor는 없습니다.

이 아이디어를 바탕으로 코드를 작성했습니다.

💻 코드 (Python)

제가 직접 작성한 코드와 주석입니다.

Python

from typing import List # List는 이 문제에서 직접 사용되지 않지만, 일반적인 LeetCode 환경을 위해 포함될 수 있습니다.

# GCD 존재하려면 str1,str2 둘다 반복문자이거나 아니면 str1자체가 str2의 반복문자여야함.
# 반복문자인지 확인하려면 두문자열의 길이의 최대공약수를 구하고
# 최대공약수의 약수의 길이만큼의 문자열의 배수가 원래 문자열이 되야함.

class Solution:

    def gcd(self, a: int, b: int) -> int:
        """두 정수의 최대공약수를 유클리드 호제법으로 계산합니다."""
        while b: #b가 0이 될때까지 반복
            a, b = b, a % b
       ...