[Array/String][Easy] 1071. Greatest Common Divisor of Strings

https://leetcode.com/problems/greatest-common-divisor-of-strings/description/?envType=study-plan-v2&envId=leetcode-75

Greatest Common Divisor of Strings - LeetCode

 

Q. str1과 str2가 주어질때, 두 string을 공통으로 나누는 base String이 존재한다. 이 base string의 최대를 구하라. 

 

두 string을 baseStr이 동시에 나눈다고 했으므로, 

 

str1 = baseStr +.. + baseStr;

str2 = baseStr + ... + baseStr;

인 것이다. 

따라서 두 수에 공통반복이 존재하므로, 

str1 + str2 == str2 + str1 이어야 한다.

이 조건을 만족하면, 서로 문자안에 공통 string으로 구성된 문장들이라는 조건이 만족한다.

 

이 중에 가장 큰 녀석을 찾는다.

서로 동일 반복 string의 집합이므로, 이는 두 string의 length에 대한 최대공약수값과 일치하게 된다.

 

string gcdOfStrings(string str1, string str2)
{
    // str1가 str2로 나눠지는 최대 string을 찾아라.
    if (str1 + str2 != str2 + str1)
        return "";

    int iGCD = gcd(str1.length(), str2.length());
    return str1.substr(0, iGCD);
}

 

Difficulty : Easy

Key : Algorithm

Time complexity : O(m+n)

  string덧붙이고 같은지 확인하는 연산에 O(m+n) 소요.

  GCD 함수 자체는 유클리드알고리즘을 사용하여 log(mxn) 따라서 최종 O(m+n)

Space complexity : O(m+n) - 덧붙이는 연산에 의하여.

Comment : 풀이법(알고리즘)을 모르면 hard고 알면 easy다.....