LeetCode: 1071

풀이

• 두 문자열에서 모두 나누어 떨어지는 특정 문자열 x들 중 가장 긴 문자열
• 두 문자열 중 더 작은 문자열의 길이부터 시작
  - 더 긴 문자열로 시작하면 짧은 문자열을 비교할 이유가 없기 때문
• 특정 문자열 x로 replaceAll을 진행했을 때, 두 문자열 모두 빈 문자열이 된다면 true!

GCD 알고리즘이란?
GCD(Greatest Common Divisor, 최대공약수) 알고리즘은
두 개 이상의 정수에서 공통으로 나누어떨어지는 가장 큰 수를 구하는 알고리즘입니다.

• 해답

/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
var gcdOfStrings = function(str1, str2) {
    let left = 0, right = 0;

    let sStr = "", lStr = "";

    let answer = "";

    if(str1.length > str2.length) {
        sStr = str2;
        lStr = str1;
    } else {
        sStr = str1;
        lStr = str2;
    }

    for(let i=1; i<=sStr.length ;i++) {
        const tmp = sStr.slice(0, i);
        if(
            sStr.replaceAll(tmp,'').length  === 0 
            && lStr.replaceAll(tmp,'').length  === 0
        ) answer = tmp
    } 
    
    return answer;
};

• Solution을 보고 수정한 해답

  처음부터 더 작은 문자열부터 시작한다면 계산 횟수를 줄일 수 있다는 생각을 하지 못했다..
  풀긴했지만 문자열이 더 길어진다면 시간초과가 발생할 수도 있을것같다.

/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
var gcdOfStrings = function(str1, str2) {
   
    let len1 = str1.length, len2 = str2.length;

    const isValid = (k) => {
        if(len1 % k === 0
            && len2 % k === 0
        ) {
            const tmp = str1.slice(0, k)
            return str1.replaceAll(tmp, "") === "" &&
            str2.replaceAll(tmp,"") === ""
        } else {
            return false;
        }
    }

    for(let i = Math.min(len1, len2); i > 0; i--) {
        if(isValid(i)) {
            return str1.slice(0, i)
        }
    }

    return "";
};

GCD(최대공약수) 구하는 법

//a가 더 큰 수!
function gcd(a, b) {
  if (b === 0) return a;
  return gcd(b, a % b);
}