[LeetCode] 1071. Greatest Common Divisor of Strings

출처 : https://leetcode.com/studyplan/leetcode-75/

 

1. 문제

 

문제 설명

두 문자열 str1과 str2가 주어졌을 때, 두 문자열을 모두 나눌 수 있는 가장 긴 공통 문자열을 구하는 문제입니다.

문자열 t가 문자열 s를 나눌 수 있으려면, 다음 조건을 만족해야 합니다.

• s = t + t + ... + t (t가 반복되어 s를 구성)

 

예시

• 입력: str1 = "ABCABC", str2 = "ABC" → 출력: "ABC"
• 입력: str1 = "ABABAB", str2 = "ABAB" → 출력: "AB"
• 입력: str1 = "LEET", str2 = "CODE" → 출력: ""

 

실제 문제

For two strings s and t, we say "t divides s" if and only if s = t + t + t + ... + 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.


Example 1:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"


Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"


Example 3:

Input: str1 = "LEET", str2 = "CODE"
Output: ""
 

Constraints:

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

 

 

2. 풀이

 

해결 방법

실제 문제는 다음과 같이 풀이했다.
그러나 "최대 공약수를 통해 패턴의 길이 한정"하는 개념을 절대 떠올리지 못해 도움을 (조금?) 받았다. 분하다.

1. 최대 공약수(GCD) 계산
   • 두 문자열의 길이를 기준으로 GCD를 계산
   • GCD는 두 문자열을 모두 나눌 수 있는 공통 패턴의 최대 길이를 의미
2. 후보 패턴 추출
   • GCD 길이만큼 str1 또는 str2의 앞부분을 잘라서 후보 패턴을 생성
3. 후보 패턴 검증
   • 후보 패턴이 두 문자열을 동일하게 구성할 수 있는지 확인
   • 후보 패턴을 반복(repeat)해서 str1과 str2가 만들어지는지 비교
4. 결과 반환
   • 검증에 성공하면 후보 패턴을 반환
   • 실패하면 빈 문자열 ""을 반환

 

실제 코드

class Solution {
    fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)

    fun gcdOfStrings(str1: String, str2: String): String {
        // 1. 두 문자열 길이의 최대 공약수
        /**
            Example 1 : 6, 3 = 3
            Example 2 : 6, 4 = 2
            Example 3 : 4, 4 = 4
        */
        val lengthGcd = gcd(str1.length, str2.length)

        // 2. 패턴 후보 추출
        val candidate = str2.substring(0, lengthGcd)

        // 3. 검증
        if (str1 == candidate.repeat(str1.length / lengthGcd) &&
            str2 == candidate.repeat(str2.length / lengthGcd)) {
            return candidate
        }

        return ""
    }
}

 

 

 

3. 배운 점

 

주요 개념

그래서 이 문제를 통해 다시 상기시킨 주요 문법은 다음과 같다.
문법이 적은 이유는 문법보다 문제의 접근 방식에 대해 다시금 상기시키게 된 것이 많다.

1. GCD
   • Kotlin의 GCD 직접 구현 방식
2. 문자열 반복
   • text.repeat(n) → 문자열을 n번 반복하여 반환

 

실제 메모

1. how to approach problem

1-1. 패턴의 길이는 두 수(문자열의 길이)의 최대 공약수를 넘어갈 수 없다.

1-2. gcd(최대 공약수) 구하기 : 유클리드 호제법

1-2-1. single-expression funcion
fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
// gcd(6, 4) = gdc(4, 2) = gcd(2, 0) = 2

1-2-3. 참고
https://namu.wiki/w/유클리드%20호제법

1-3. 패턴 후보 추출은 단순히 두 문자열 중 하나를 선택하여, 0번째 인덱스부터 자르면 된다.

2. repeat string

2-1. string.repeat(n) // n=number(int)