728x90
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
https://mathbang.net/206#google_vignette
최대공약수와 최소공배수의 관계
최대공약수와 최소공배수를 구하는 방법을 이해했나요? 대부분의 경우에 최대공약수와 최소공배수는 소인수분해를 이용하는 방법으로 구해요. 이 방법은 초등학교 때 많이 해봤던 방법이니까
mathbang.net
처음에는 긴 문자를 기준으로 반복을 돌려줬었는데
그렇게 하면 (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);
}
}
728x90
'SW Expert Academy > SWEA D3' 카테고리의 다른 글
| [SW Expert Academy] 세가지 합 구하기 (D3) (0) | 2024.09.27 |
|---|---|
| [SW Expert Academy] 문자열 교집합 (D3) (0) | 2024.09.27 |
| [SW Expert Academy] 전봇대 (D3) (0) | 2024.09.20 |
| [SW Expert Academy] 이진수 표현 (D3) (0) | 2024.09.20 |
| [SW Expert Academy] 문제 제목 붙이기 (D3) (0) | 2024.09.20 |