[SW Expert Academy] 15758. 무한 문자열 - 자바

https://swexpertacademy.com/main/code/problem/problemSubmitDetail.do

SW Expert Academy

우선 조건을 보면 80개의 테스트 케이스에 대해 한 문자열은 50자 이하로 자바는 시간제한 2초로 데이터가 많지 않아 다소 쉽게 접근할 수 있다.

실패 사례

처음 시도했던 방법은 짧은 문자열을 찾아 이 문자열로 긴 문자열을 짧은 문자열의 길이만큼 쪼개며 같은지 비교하는 로직을 작성했다.
이 방법으로는 ababab abab가 들어올 때 no를 반환해서 실패하였고 이 경우에 대해 처리할 수 있는 로직이 필요했다.

문제 풀이

사실 문자열을 무한대로 붙이는 건 불가능하다. 그럼 어떻게 판별할까? 각 문자열에 대해 그 문자열 그대로 자기 자신에 더했을 때 두 문자열의 길이가 같아지는 때가 있을 것이다.
위 예시로 ababab와 abab가 같아지는 시점은 abababababababababab이다. 이렇게 한번 같아지는 시점을 찾으면 이 두 문자열은 무한대로 늘렸을 때도 같을 것이다.
그럼 이 시점을 어떻게 찾을까?

두 문자열의 최소공배수를 찾는다

각 문자열을 두 문자열의 최소공배수가 될 때까지 이어붙였을 때 두 문자열이 같으면 두 문자열은 yes를 반환하게 만들 것이다.

코드

import java.util.Scanner;

class Solution
{
    public static long lcm(long a, long b) {
        int gcd_value = gcd((int)a, (int)b);

        if (gcd_value == 0) return 0; // 인수가 둘다 0일 때의 에러 처리

        return Math.abs( (a * b) / gcd_value );
    }
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return Math.abs(a);
    }
    public static void main(String args[]) throws Exception
    {

        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();

        for(int test_case = 1; test_case <= T; test_case++)
        {
            String str1 = sc.next();
            String str2 = sc.next();
            int len1 = str1.length();
            int len2 = str2.length();
            long lcm = lcm(len1, len2);
            String result1 = "";
            String result2 = "";
            for (int i = 0; lcm != i * len1; i++) {
                result1 += str1;
            }
            for (int i = 0; lcm != i * len2; i++) {
                result2 += str2;
            }
            System.out.printf("#%d ",test_case);
            System.out.println(result1.equals(result2) ? "yes" : "no");
        }
    }
}

조금만 깊게 생각한다면 알고리즘도 쉽게 설계 가능하고 코드도 어려운 부분 없는 문제이다.