728x90
프로그래머스 풀 때도 봤던 문제.
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 (i.e., t is concatenated with itself one or more times). Given two strings str1 and str2, return t
leetcode.com
만약,,, 나눠지지 않는다면, 두 문자열을 서로 교차해서 붙여 같은지 비교해본다. 여기서 두 문자열이 다르다면! 나눌 수 없는 문자열이다.
만약,,, 나눠진다면, 두 문자열의 최대공약수를 구해 하나의 문자열에 0 부터 최대공약수 값 만큼의 문자열을 반환하면 된다.
class Solution {
func gcdOfStrings(_ str1: String, _ str2: String) -> String {
guard str1 + str2 == str2 + str1 else { return "" }
let count = gcd(str1.count, str2.count)
return String(str1.prefix(count))
}
private func gcd(_ a: Int, _ b: Int) -> Int{
if (b == 0) { return a }
return gcd(b, a % b)
}
}최대 공약수, 최대 공배수 코드는 볼 때 마다 생각이 안나서 정리를 해둬야겠다.
func gcd(_ a: Int, _ b: Int) -> Int{
if (b == 0) { return a }
return gcd(b, a % b)
}
func lcm(_ a: Int, _ b: Int) -> Int {
return a * b / gcd(a, b)
}728x90