707's devlog

[Leetcode75] 2. Greatest Common Divisor of Strings

707's photo
707
·

4 min read

[1] 문제

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 the largest string x such that x divides both str1 and str2.

두가지 문자열을 받아 해당 문자열의 최대공약수(최대공약문자열???)을 구하는 문제이다!

<example>

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Input: str1 = "LEET", str2 = "CODE"
Output: ""

+ 내가 중간에 걸렸던 케이스

Input: str1 = "ABCDEF", str2 = "ABC"
Output: ""

이 케이스는 str1 이 아예 약수로 나눠지지 않는 문자열이기 때문에 output 은 무조건 ""으로 빈 문자열이 되어야한다.

[2] 풀이

function gcdOfStrings(str1: string, str2: string): string {
  // 두 문자열 길이의 공약수 길이 배열
  const availableCd = [];
  const shortLen = str1.length > str2.length ? str2.length : str1.length;
  for (let i = 1; i <= shortLen; i++) {
    if (str1.length % i == 0 && str2.length % i == 0) {
      availableCd.push(i);
    }
  }

  // 문자열의 최대공약수
  let gcdStr = "";
  for (let i = 0; i < availableCd.length; i++) {
    const currentCdStirng = str1.substring(0, availableCd[i]);
    let tempStr = "";
    let tempStr2 = "";

    for (let j = 0; j < str1.length / availableCd[i]; j++) {
      tempStr += currentCdStirng;
    }
    for (let k = 0; k < str2.length / availableCd[i]; k++) {
      tempStr2 += currentCdStirng;
    }
    if (tempStr == str1 && tempStr2 == str2) {
      gcdStr = currentCdStirng;
    }
  }

  return gcdStr;
}

  1. 먼저 두 문자열길이에서 나올수있는 공약수를 구한다. "ABC"와 "ABCABC"라면 gcd문자열의 길이는 1과 3만 가능하다.

  2. 가능한 공약수 길이가 담긴 배열([1, 3])을 순회하며 해당 길이만큼을 str1에서 자른 것을 currentCdString으로 한다.

  3. str1과 str2의 길이만큼 currentCdString을 반복하고, 반복시킨 문자열이 원래의 문자열인 str1, str2와 일치하는지를 확인한다. 일치한다면 그 문자열은 새로운 gcdStr이 된다.

  4. 공약수 길이 배열을 순회하면서 점점 더 높은 길이를 currentCdString으로 하며, 3번의 조건이 일치한다면 그게 기존것보다 더 큰 최대공약수이기때문에 gcdStr을 교체한다.

여기서 몇가지 수정을 해보면 좋을 것 같다

  1. 중간에 str1의 substring 값과 str2의 substring 값을 비교해서 다르다면 바로 return해버리기

  2. 가능한 공약수 배열을 앞쪽부터가 아니라 뒤쪽부터 순회를 하도록 해 더 큰 수부터 찾도록 해보기

수정해서 시간, 메모리적으로 더 효율적인 결과가 나오는지 테스트 해봐야겠다.

[2-1] 풀이 1

function gcdOfStrings(str1: string, str2: string): string {
  // 두 문자열 길이의 공약수 길이 배열
  const availableCd = [];
  const shortLen = str1.length > str2.length ? str2.length : str1.length;
  for (let i = 1; i <= shortLen; i++) {
    if (str1.length % i == 0 && str2.length % i == 0) {
      availableCd.push(i);
    }
  }

  // 문자열의 최대공약수
  let gcdStr = "";
  for (let i = 0; i < availableCd.length; i++) {
    const currentCdStirng = str1.substring(0, availableCd[i]);
    if(currentCdStirng != str2.substring(0, availableCd[i])) {
        continue;
    } // 🚀 이 조건을 추가했다.

    let tempStr = "";
    let tempStr2 = "";

    for (let j = 0; j < str1.length / availableCd[i]; j++) {
      tempStr += currentCdStirng;
    }
    for (let k = 0; k < str2.length / availableCd[i]; k++) {
      tempStr2 += currentCdStirng;
    }
    if (tempStr == str1 && tempStr2 == str2) {
      gcdStr = currentCdStirng;
    }
  }

  return gcdStr;
}

기존 결과에서 조금 더 좋아진? 근데 보니까 런타임은 같은 코드도 돌릴때마다 달라져서 유의미한지는 잘 모르겠다..

[2-2] 풀이2

function gcdOfStrings(str1: string, str2: string): string {
  // 두 문자열 길이의 공약수 길이 배열
  const availableCd = [];
  const shortLen = str1.length > str2.length ? str2.length : str1.length;
  for (let i = 1; i <= shortLen; i++) {
    if (str1.length % i == 0 && str2.length % i == 0) {
      availableCd.push(i);
    }
  }

  // 문자열의 최대공약수
  let gcdStr = "";
  for (let i = 0; i < availableCd.length; i++) {
    const currentCd = availableCd.pop();
    const currentCdStirng = str1.substring(0, currentCd);
    if(currentCdStirng != str2.substring(0, currentCd)) {
        continue;
    }

    let tempStr = "";
    let tempStr2 = "";

    for (let j = 0; j < str1.length / currentCd; j++) {
      tempStr += currentCdStirng;
    }
    for (let k = 0; k < str2.length / currentCd; k++) {
      tempStr2 += currentCdStirng;
    }
    if (tempStr == str1 && tempStr2 == str2) {
      gcdStr = currentCdStirng;
      break;
    }
  }

  return gcdStr;
}

큰 공약수부터 찾아 조건에 맞으면 바로 break로 for문을 빠져나오도록 했다.

흠.. 별로 달라지진 않는다;; 특히 메모리 사용량이 너무 크다.

[3] 참고용

const gcdOfStrings = (str1, str2) => {
  // If the concatenated strings are not equal,
  // then a common divisor cannot be found
  if (str1 + str2 !== str2 + str1) {
    return '';
  }

  // Calculate the greatest common divisor of the string lengths
  const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));
  const len = gcd(str1.length, str2.length);

  // Return the substring that is a common divisor
  return str1.substring(0, len);
};

먼저 두 문자열이 반복이 되는 문자열인지를 확인해본다. 저걸 저렇게 두 문자열의 덧셈이 같은지를 확인하는 식으로 처리한 게 !! 했던 부분이고

gcd를 구하는 것은 재귀함수를 이용한것도 오! 하는 느낌.

저렇게 반복 여부를 미리 확인 하고나면 무조건 length의 최대공약수가 두 문자열의 gcdString이 되기때문에... 엄청 간단하게 구할 수가 있는 것이다.

leetcodeTypeScript