[Java] LeetCode 1071: Greatest Common Divisor of Strings

[문제 바로 가기] - Greatest Common Divisor of Strings

문제 해석

문자열 str1과 str2가 주어질 때 두 문자열을 동시에 나누는 문자열 중에서 가장 긴 문자열 x를 구해라.

---

아이디어

easy지만 도무지 아이디어가 떠오르지 않아 클로드한테서 힌트를 받아냈다.

1. x의 길이는 str1, str2 길이의 최대 공약수
2. x는 str1와 str2의 접두사
3. str1 = "AAAAAB", str2 = "AAA"의 경우를 위해서 후보를 구한 뒤 나눠지는지 반드시 확인

그래서 아래와 같이 코드를 작성했다.

---

풀이

첫번째 풀이

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();

        // largest string x
        for (int i = Math.min(len1, len2); i >= 1; i--) {
            if (len1 % i == 0 && len2 % i == 0) {
                // 길이가 i인 문자열로 str1, str2이 나눠지는지 확인
                
                String newStr1 = "";
                String newStr2 = "";

                String prefix = str1.substring(0, i);

                for (int j = 0; j < len1 / i; j++) newStr1 += prefix;
                for (int j = 0; j < len2 / i; j++) newStr2 += prefix;
                
                if (str1.equals(newStr1) && str2.equals(newStr2)) return prefix;
            }
        }
        
        return "";
    }
}

다만 이 코드는 최대공약수를 구하는 코드가 아니라고 생각해 그 부분을 수정했다.
왜냐하면 if (len1 % i == 0 && len2 % i == 0)를 처음으로 통과하는 i가 gcd가 되는 것이며 gcd가 실패한다면 다른 공약수는 무조건 실패하게 된다. 따라서 나의 풀이에서 if문 안에 break가 필요하다.

그리고 나는 힌트 그대로 최대 공약수의 길이를 구한 뒤 후보를 검증해봐야 한다고 생각했다. 하지만 굳이 for문을 이용해서 후보를 검증할 필요는 없고, if (!(str1 + str2).equals(str2 + str1))로도 충분히 검증할 수 있음을 다른 코드를 보고 알았다.

두번째 풀이

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();

        if (!(str1 + str2).equals(str2 + str1)) return "";

        String result = str1.substring(0, gcd(len1, len2));
        return result;
    }

    int gcd(int num1, int num2) {
        if (num2 == 0) return num1;

        return gcd(num2, num1 % num2);
    }
}