[백준] S5 12871번 무한 문자열 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

12871번: 무한 문자열

[문제] 

문자열 s가 있을 때, f(s)는 s를 무한번 붙인 문자열로 정의한다. 예를 들어, s = "abc" 인 경우에 f(s) = "abcabcabcabc..."가 된다.

다른 문자열 s와 t가 있을 때, f(s)와 f(t)가 같은 문자열인 경우가 있다. 예를 들어서, s = "abc", t = "abcabc"인 경우에 f(s)와 f(t)는 같은 문자열을 만든다.

s와 t가 주어졌을 때, f(s)와 f(t)가 같은 문자열을 만드는지 아닌지 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 s, 둘째 줄에 t가 주어진다. 두 문자열 s와 t의 길이는 50보다 작거나 같은 자연수이고, 알파벳 소문자로만 이루어져 있다. 

[출력]

첫째 줄에 f(s)와 f(t)가 같으면 1을, 다르면 0을 출력한다.

 

 

---

[풀이]

1. 두 문자열의 길이의 최소 공배수를 구해준다.

2. 최소 공배수의 길이만큼 각 문자열을 늘려준다.

3. 두 문자열을 비교해서 결과에 맞는 값을 출력한다. (같으면 1, 아니면 0)

[접근]

1. 처음에는 더 긴 문자열을 replace로 없애주면 될거라고 생각했었다.

2. 하지만 긴 문자열의 경우도 같이 길이를 증가시켜줘야되는 경우도 발생한다.

3. 문자열을 서로 늘릴 때, 길이가 같아지는 경우는 최소 공배수일 경우이므로 최소 공배수를 구해 해당 길이만큼 늘려준다.

[코드]

package BOJ_silver;

import java.io.*;
import java.util.*;

public class Main_S5_12871 {
	static String s;
	static String t;
	static int len;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		s = br.readLine();
		t = br.readLine();
		
		String S = s;
		String T = t;
		
		if (s.length() != t.length()) {
			// 두 문자열의 길이의 최소 공배수를 구해준다.
			len = lcm(s.length(), t.length());
			
			// 구해진 최소 공배수만큼 증가시켜준다.
			while (S.length() != len)
				S += s;
			
			while (T.length() != len)
				T += t;
		}
		
		if (S.equals(T))
			System.out.println(1);
		else
			System.out.println(0);
	}
	
	// 최대 공약수
	public static int gcd(int a, int b) {
		while (b > 0) {
			int temp = a;
			a = b;
			b = temp % b;
		}
		
		return a;
	}

	// 최소 공배수 => (a * b) / a와 b의 최대 공약수
	public static int lcm(int a, int b) {
		return (a * b) / gcd(a, b);
	}
}