[LeetCode][Java][영어공부] 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

concatenate : 연결하다. 연관시키다.

i.e : that is의 라틴어, 앞의 문장을 요약해서 다시말해줄 때 -> "즉, 다시말해"

str1 을 앞에서부터 자르면서 prefix를 하나씩 만들고 다 비교해가면 풀 수 있을 것 같았다.
하지만 구현난이도가 많이 높아보였고 
다른 풀이를 생각해봤다.

일단 gcd가 있냐 없냐를 보면
X = gcd
A = XXXX,   B = XXX 이렇게 같은 문자열이 반복되는 구조라면
AB = BA 라는 것을 이용해서 걸러준다.

gcd를 구하는 방법은

 

gcd 가 X 라 가정하고 x = X.length()

gcd로 이루어진 임의의 문자열 2개
str1 = XXXX ...  = X * n
str2 = XXX  ... = X * m 

이 말은 두개의 문자열의 길이는 x의 배수여야한다.
그 말은 x = gcd(str1, str2) 라는 것을 알 수 있다.
정답의 길이를 알았으면 그만큼 자르면 정답이 될 수 있다.

n = 4 , m = 3 이라 가정하자
위의 계산을 문자열의 길이로 생각하고 최대공약수를 구한다면
gcd(4x, 3x) = x * gcd(4, 3) = x 이라는 것을 알 수 있다.

이것을 통해서 정답의 길이를 구하고 str1에서 0번째 인덱스에서 gcd - 1 인덱스 까지 자르면 정답이 나온다.

gcd 구하는 법
https://mirrorpi.tistory.com/entry/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98

유클리드 호제법 - 최대공약수 구하기(+ 최소공배수)

 

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if(!(str1 + str2).equals(str2 + str1)) return "";

        int gcdLen = gcd(str1.length(), str2.length());
        return str1.substring(0, gcdLen);
    }

    public int gcd(int a, int b) {
        while(b != 0) {
            int temp = a%b;
            a = b;
            b = temp;
        }
        return a;
    }
}