1071. Greatest Common Divisor of Strings

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

팀 알고리즘 레포지토리 주소

문제 출처

두 문자열의 최대공약 문자?를 구해라. 

[문제 설명]

t가 a번 반복되는 문자 배열은 str1 = t+t+t+t....+t => a*t

t가 b번 반복되는 문자 배열은 str2 = t+t+t+...+t=> b*t

t를 구하시오.

 

[처음 생각한 접근 방법]

결국에 최대공약수를 구하는 게 핵심인 문제다.
최대 공약수 구하는 법은 그냥 검색해봤다. 원래 그냥 일차 검색하려했는데 유클리드 호제법이라는 게 있는 걸 알아서.

출처는 링크

최대공약수(GCD), 최소공배수(LCM) 구하기 유클리드 호제법 알고리즘 :: 코드자몽

str1의 길이가 a, str2의 길이가 b라고 하자.

그러면 a와 b의 최대 공약수인 c를 구하고, 문자열에서 c개를 뽑은 것이 반복될 수 있는 기준 문자열이 된다.

최대 공약수란 두 수를 나눌 수 있는 최대의 값이다.

str1의 길이가 6, str2의 길이가 3으로 주워줬다면 answer의 길이는 최대공약수인 3.

str1과 str2 모두 answer을 반복해서 만든 문자열이므로 둘 중 아무한테서나 앞에서부터 3문자를 뽑으면 반복할 문자열이 되어야 한다.

str1을 3글자씩 나눠서 answer과 같은지 확인 후 모두 같으면 str1은 answer을 반복한 문자열이 된다.

str2도 마찬가지로 3글자씩 나눠서 answer과 같은지 확인 후 모두 같으면 str2는 answer을 반복한 문자열이 된다.

 

예)

str1=ABCABC, str2=ABC

-> answer은 str1에서 두 수의 최대 공약수의 개수만큼 뽑은 문자열 "ABC"가 된다.

-> str1이 answer을 반복한 건지 체크, 맞으면 str2를 체크하러 감
아니면? answer은 반복문자열이 아니므로 return ""

-> str2가 answer을 반복한 건지 체크, 맞으면 str1, str2를 반복한 문자열이 됩니다.
아니면? answer은 반복문자열이 아니므로 return "";

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        // 최대 공약수 구하기
        int gcd = getGCD(Math.max(str1.length(), str2.length()), Math.min(str1.length(), str2.length()));
        // 최대 공약 문자열 구함
        String answer = str1.substring(0, gcd);

        // str1이 answer을 반복하는지 확인
        for (int i = 0; i <= str1.length()-gcd; i+=gcd) {
            // 반복하지 않으면, 공약 문자열은 없음
            if (!str1.substring(i, i+gcd).equals(answer)) {
                return "";
            }
        }
        // str2가 answer을 반복하는지 확인
        for (int i = 0; i <= str2.length()-gcd; i+=gcd) {
            // 반복하지 않으면, 공약 문자열은 없음
            if (!str2.substring(i, i+gcd).equals(answer)) {
                return "";
            }
        }

        // 전부 answer을 반복하고 있으므로 answer을 리턴
        return answer;
    }

    public int getGCD(int a, int b) {
        while(b > 0) {
            int tmp = a;
            a = b;
            b = tmp%b;
        }
        return a;
    }
}

[리트코드 답안]

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);
}

리트코드 답안을 볼 때마다 정말 화가 난다.

str1,str2 모두 같은 문자열의 반복이므로 둘이 순서를 바꿔서 더해도 당연히 같아야 하는데, 그걸 이용해서 초기에 잘 걸러줬다.