[SWEA] 15758 - 무한 문자열 (Java)

Problem

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AYP5JmsqcngDFATW&categoryId=AYP5JmsqcngDFATW&categoryType=CODE&problemTitle=15758&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

Approach & Logic

이 문제의 키포인트는 최소공배수!
첫번째 예제인 ababab, abab에서 각각의 문자열 길이가 6, 4이니까 최소공배수는 12이다.
즉, 각 문자열의 길이가 12가 되도록 만들어서 두 문자열을 비교하면 그 결과가 무한히 반복했을때의 결과이다.

최대공약수(GCD) 구하기

(1) java.math.BigInteger를 사용한 gcd 함수 구현

String a = "ababab";
String b = "abab";

BigInteger alength = BigInteger.valueOf(a.length());
BigInteger blength = BigInteger.valueOf(b.length());

int gcd = alength.gcd(blength).intValue();

(2) 재귀를 사용한 gcd 함수 구현

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

최소공배수(LCM) 구하기

int a = 5;
int b = 15;
int lcm = a * b / getGcd(a, b);

Code

package SWEA;

import java.util.*;
import java.io.*;
import java.math.BigInteger;

public class swea_15758 {

    //결과값 저장하기 위한 변수
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer str = new StringTokenizer(br.readLine());
        int num = Integer.parseInt(str.nextToken());

        for(int i=1; i<=num; i++) {
            String answer = "no";
            str = new StringTokenizer(br.readLine());
            String a = str.nextToken();
            String b = str.nextToken();

            //최소공배수 구하기
            BigInteger alength = BigInteger.valueOf(a.length());
            BigInteger blength = BigInteger.valueOf(b.length());
            int gcd = alength.gcd(blength).intValue();
            int lcm = (a.length() * b.length()) / gcd;

            //같은 길이(최소공배수만큼)를 갖도록 A, B 문자열 늘리기
            String A = a;
            String B = b;
            while(A.length()!=lcm) {
                A+=a;
            }
            while(B.length()!=lcm) {
                B+=b;
            }

            if(A.equals(B)) {
                answer="yes";
            }

            sb.append("#"+i+" "+answer+"\n");
        }

        System.out.print(sb);

    }
}