[LeetCode/JAVA] 071. Greatest Common Divisor of Strings

 

 

https://github.com/ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다. 😊
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
참여 문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

문제 출처 : https://leetcode.com/problems/greatest-common-divisor-of-strings/

문제 설명

출처 : LeetCode

문자열 t로 반복되는 두 문자열이 있습니다.
어떤 문자열로 반복되는지 가장 길이가 긴 t를 반환하세요.

즉, 두 문자열의 최대공약수를 구하는 문제

풀이 방법

최대공약수를 구해야 하므로 문자열을 끝에서 하나씩 잘라서 비교
str1과 str2를 치환해서 모두 치환이 되면 최대공약수로 판단

내 코드(JAVA)

 

public class Sanghoo {

    // 1번 방법 : replaceAll 사용
    public String gcdOfStrings(String str1, String str2) {
        String res = "";

        for(int i=str2.length(); i>0; i--) {
            String regex = str2.substring(0, i);

            String temp1 = str1.replaceAll(regex, "");
            String temp2 = str2.replaceAll(regex, "");

            if (temp1.isEmpty() && temp2.isEmpty()) {
                res = regex;
                break;
            }
        }

        return res;
    }

    // 2번 방법 : 배열 사용
    public String gcdOfStrings_2(String str1, String str2) {
        String res = "";

        for(int i=str2.length(); i>0; i--) {
            String regex = str2.substring(0,i);
            String[] arr1 = str1.split(regex);
            String[] arr2 = str2.split(regex);

            if(arr1.length == 0 && arr2.length == 0) {
                res = regex;
                break;
            }
        }

        return res;
    }

}

 

2가지 방법이지만 접근 방법은 동일하고, 성능에도 차이가없다.

사실 둘다 성능은 최악이다..😂

 

이미 성능은 최악이지만 그나마 리팩토링을 해본다면

str2를 기준으로 잡지말고 str1과 str2중에 길이가 짧은 문자열을 기준으로 잡아줘도 될 것 같다.

 

다른 사람 코드

 

public String gcdOfStrings(String str1, String str2) {
    if (!(str1+str2).equals(str2+str1))  return "";
    
    int gcdVal = gcd(str1.length() , str2.length());
    return str2.substring(0, gcdVal);
}

public static int gcd(int p, int q) {
    if (q == 0) return p;
    else return gcd(q, p % q);
}

 

리트코드 추천 답안인데, 수학적으로 접근해서 풀었다. 😢

유클리드 호제법? gcd 메서드를 통해 최대 공약수가 될 길이를 구한다.

수학 잘 하고싶다..ㅎㅎ