내 즙을 짜낸 Greatest Common Divisor of Strings

LeetCode: Greatest Common Divisor of Strings

 

문제 보기

 

1트

var gcdOfStrings = function(str1, str2) {
/*함수 안의 새로운 함수 gcdGen이 있습니다. 이 함수는:
한쪽이 다른 한쪽에 전혀 포함되지 않으면 일단 빈 문자열을 리턴합니다.
그렇지 않으면 s1이 s2의 '배수'인지 확인하고(즉, s2를 여러번 더하면 s1이 되는지 확인하고)
맞다면 s2를 리턴, 아니라면 s1에서 s2를 제거하고 다시 s2와 gcdGen을 돌려 주는 재귀함수입니다.
*/
    const gcdGen = function (s1, s2) {
        if(!s1.includes(s2) && !s2.includes(s1)) return ''
        return (s1.replaceAll(s2, '') === '') ? s2 : gcdGen(s2, s1.replace(s2, ''))}
    return gcdGen(str1, str2)
};

📎 첫 시도에 재귀를 이용해서 풀고 싶었습니다..

그렇지만 ‘AABB’, ‘AB’인 경우에 걸려서 통과하지 못했습니다…

답은 ‘’이지만 제 알고리즘에서는 ‘AB’가 나옵니다. str1에서 str2를 제거하고 나면 ‘AB’가 나오기 때문입니다.

 

2트

/*한쪽이 다른 쪽에 전혀 포함되지 않으면 빈 문자열을 리턴합니다.
둘 중 짧은 문자열을 변수 s로 선언하고
s가 빈 문자열이 될때까지 s의 길이를 끝부터 줄여가면서 str1과 str2가 s의 '배수'인지 확인합니다.
배수가 되면 반복을 종료하고 s를 리턴합니다.
*/
var gcdOfStrings = function(str1, str2) {
    if(!str1.includes(str2) && !str2.includes(str1)) return ''
    let s = [str1, str2].sort((a,b) => a.length - b.length)[0]
    while(s !== ''){
        if(str2.replaceAll(s, '') === '' && str1.replaceAll(s, '') === '') break;
        else s = s.slice(0, s.length-1)
    }
    return s
};

📎 그래서 그냥 정직하게 풀었습니다. 그렇지만 저는 재귀를 이용해서 너무 풀고 싶었습니다… 그래서….

 

다른 사람의 풀이

const gcdOfStrings = (str1, str2) => {
  if (str1 + str2 !== str2 + str1) return '';
  const gcd = (a, b) => (0 === b ? a : gcd(b, a % b));
  return str1.substring(0, gcd(str1.length, str2.length));
};

📎 이 풀이를 찾아냈습니다.

놀랍게도 그냥 길이의 최대공약수를 재귀 함수로 찾아서 substring으로 해결합니다.

정말 생각지도 못한 풀이… 저는 그냥 알고리즘 공부를 중단하는 게 낫겠습니다.🥲