[SW Expert Academy] 무한 문자열 (D3)

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

SW Expert Academy

 

https://mathbang.net/206#google_vignette

최대공약수와 최소공배수의 관계

처음에는 긴 문자를 기준으로 반복을 돌려줬었는데

그렇게 하면  (S.length()>T.length())라고 가정.
T가 abab 중에 ab까지 밖에 가지 못했음에도 yes가 나올 수 있다.

 

따라서 본 문제는 최대공약수를 이용한 최소공배수 문제로 해결해야한다.

import java.util.Scanner;

class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int t = sc.nextInt();

		for (int tc = 1; tc <= t; tc++) {

			String S = sc.next();
			String T = sc.next();

			boolean isPossible = true;

			int length = lcm(S.length(), T.length());

			for (int i = 0; i < length; i++) {
				if (S.charAt(i % S.length()) != T.charAt(i % T.length())) {
					isPossible = false;
				}
			}
			
			if(isPossible) {
				System.out.println("#"+tc+" "+"yes");
			}
			else {
				System.out.println("#"+tc+" "+"no");
			}

		}

	}

	public static int lcm(int a, int b) { //최소공배수
		return (a * b) / gcd(a, b);
	}

	public static int gcd(int a, int b) { //최대공약수
		if (b == 0)
			return a;

		return gcd(b, a % b);
	}
}