[LeetCode][Java][영어공부] 1071. Greatest Common Divisor of Strings
Greatest Common Divisor of Strings - LeetCode
Can you solve this real interview question? Greatest Common Divisor of Strings - 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 st
leetcode.com
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
유클리드 호제법 - 최대공약수 구하기(+ 최소공배수)
알아야할 표현 최대공약수 = GCD = Greatest Common DivisorGCD(A, B) = A와 B의 최대공약수 유클리드 호제법 두 양수 A, B(A > B)에 대하여 A = BQ + R (0 ≤ R 즉, GCD(A, B) = GCD(B, R)R = 0이라면 A, B의 최대공약수는 B가
mirrorpi.com
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;
}
}