LeetCode 1071. Greatest Common Divisor of Strings [Java]

https://leetcode.com/problems/greatest-common-divisor-of-strings/description/?envType=study-plan-v2&envId=leetcode-75

입력으로 주어지는 두 문자열의 최대공약수(GCD)를 구하는 문제이다.
두 문자열의 최대공약수란 두 문자열 내 겹치는 가장 작은 덩어리를 의미한다.
예를 들어 ABABAB ABAB라는 두 문자열이 있을 때 이때의 gcd는 AB가 된다.

내 코드

/**
    시나리오
    1. str1과 str2의 길이 비를 구함
    2. 구한 길이 비를 이용해 각 str의 첫번째 덩어리를 구하고(ex: 길이 비==3이면 해당 문자열을 3덩어리로 쪼갬) 나머지 덩어리도 첫번째 덩어리와 일치하는지 구함
    3. 각 str의 위 조건이 참이면 str1과 str2의 덩어리가 같은지 비교, 참이면 str1나 str2의 덩어리 중 아무거나 리턴하고 거짓이면 ""리턴
 */
class Solution {
    public String gcdOfStrings(String str1, String str2) {
        int lengthGcd = calcLengthGcd(str1.length(), str2.length());
        int str1Quota = str1.length() / lengthGcd;
        int str2Quota = str2.length() / lengthGcd;

        String str1Gcd = getStrGcd(str1Quota, str1);
        if (str1Gcd.equals("")) {
            return "";
        }

        String str2Gcd = getStrGcd(str2Quota, str2);
        if(str2Gcd.equals("")){
            return "";
        }

        if(!str1Gcd.equals(str2Gcd)){
            return "";
        }

        return str1Gcd;
    }

    // 1. str1, str2 길이의 GCD
    private int calcLengthGcd(int a, int b) {
        int r = a % b;
        if (r == 0){
            return b;
        }
        return calcLengthGcd(b, r);
    }

    // 2. str이 반복문자열인지 체크
    private String getStrGcd(int lengthQuota, String str) {
        int chunkSize = str.length()/lengthQuota;
        // str이 0~res-1만큼 slice된 것의 반복인지 체크
        String sliced = slice(0, chunkSize, str);

        for (int i = chunkSize; i < str.length(); i += chunkSize) {
            String current = slice(i, i + chunkSize, str);

            if (!current.equals(sliced)) {
                return "";
            }
        }

        return sliced;
    }

    //시작인덱스, 종료인덱스를 받아 문자열을 slice해주는 메서드
    private String slice(int startIdx, int endIdx, String str) {
        StringBuilder sb = new StringBuilder();
        for (int i = startIdx; i < endIdx; i++) {
            sb.append(str.charAt(i));
        }

        return sb.toString();
    }
}

코드 샘플

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

    public int getGcd(int a, int b) {
        if(b==0) return a;
        return getGcd(b, a%b);
    }
}

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

두 문자열을 순서를 바꿔가며 붙였을 때 두 결과가 같지 않으면 최대공약수는 없다는 것이다.

만약 두 문자열의 stringGcd가 같다면 어떻게 붙여도 결국 최대공약수의 반복이 돼야하기 때문이다.
따라서 위 방법으로 두 문자열의 최대공약수 여부를 조사한 뒤, 두 문자열의 길이의 최대공약수를 구한다.
그러면 두 문자열의 한 덩어리의 길이를 구할 수 있다. 어차피 두 문자열의 stringGcd가 있는 것을 확인했으므로 str1의 한 덩어리를 리턴해준다.

 

나는 두 문자열의 길이의 최대공약수를 구해 각 문자열의 덩어리 개수를 구한 뒤, 각 문자열이 덩어리의 반복으로 이루어져있는지 구하고
두 문자열 모두 덩어리의 반복이면 두 덩어리가 같은지 비교해 정답을 리턴했다.
하지만 코드 샘플처럼 애초에 stringGcd가 있는 지 확인했다면 이 과정이 필요가 없는 것이다. 물론 실행시간을 내 코드나 샘플 코드나 같았지만 불필요한 로직을 작성하지 않는 게 더 바람직해 보인다.

새로 알게된 점

이미 문자열 slicing이 정의 돼있다. 이거 쓰자.. 사실 본적은 많은데 한번도 써본적이 없어서 적용을 못했다.