문자열의 최대 공약수 찾기 / Greatest Common Divisor of Strings

* 문제
주어진 두 문자열 str1과 str2의 가장 큰 공약수(GCD)를 찾아야 합니다.
두 문자열의 공약수는, 두 문자열을 여러 번 반복해서 만들 수 있는 문자열입니다.
예를 들어, "ABCABC"와 "ABC"는 공통적으로 "ABC"로 나뉠 수 있습니다.

* 조건
1. 두 문자열 str1, str2는 각각 길이 1 이상 1000 이하입니다.
2. 문자열은 대문자로만 이루어져 있습니다.

* 예시
1. 입력: str1 = "ABCABC", str2 = "ABC" 출력: "ABC"

2. 입력: str1 = "ABABAB", str2 = "ABAB" 출력: "AB"

3. 입력: str1 = "LEET", str2 = "CODE" 출력: "" (공통 부분이 없음)

4. 입력: str1 = "ABABABAB", str2 = "ABAB" 출력: "ABAB"

 

[정답]

String gcdOfStrings(String str1, String str2) {
  // 두 문자열을 이어 붙였을 때 결과가 같지 않으면 공통 문자열이 없음
  if (str1 + str2 != str2 + str1) {
    return '';
  }

  // 두 문자열 길이의 최대 공약수를 구함
  int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }

  // str1과 str2의 길이의 최대 공약수 만큼 문자열의 앞부분을 반환
  int gcdLength = gcd(str1.length, str2.length);
  return str1.substring(0, gcdLength);
}

[문제 해설 보고 풀이 해보기]
b의 길이가 0이면 최대 공약수는 a 
0이 아니면 a를 b로 나눈 몫을 넣고, 이 몫이 0이 아니면 계속 반복함

예시)

str1 = ababab
str2 =abab

1) gcd(str1.length, str2.length)
-> gcd(6,4)
return gcd(4,6%4)

2)gcd(4,2)
-> gcd(2,0)

-> gcd는 2임. 따라서 substring으로 잘라서 반환

[유사한 방법]
dart에 .gcd()라는 함수가 있어서 아래와 같이 작성도 가능하다.
하지만 해당 문제에서는 최대 공약수 구하는 로직이 어떻게 돌아가는지 알고 있는가를 묻고 싶은 듯하다.

int gcdLength = str1.length.gcd(str2.length);

 

[ABAB가 최대 공약수가 아닌 이유 / 답이 AB인 이유]

만약 "ABAB"가 답이라면, str1과 str2가 "ABAB"의 반복으로 이루어져야 합니다.

그러나:

• "ABAB"를 반복해서 "ABABAB"를 만들 수 없습니다.
  • "ABABAB"는 "ABAB"로 나누어떨어지지 않음 (한 번 더 반복하면 "ABABABAB"이 되어야 함)

따라서 "ABAB"는 올바른 답이 아니고, "AB"가 정답입니다.