[백준/자바] 12871 무한 문자열

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

ab
abab

예제 출력 1

1

예제 입력 2

abc
bca

예제 출력 2

0

---

알고리즘 분류

• 문자열

---

설명

두 문자열이 주어졌을때 두 문자열의 길이의 최소 공배수를 구한다.

최소 공배수의 길이만큼 두 문자열을 붙인 문자열을 만든 뒤 같은 문자열인지 판단한다.

 

코드

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	public class BOJ12871 {
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String s = br.readLine();
	String t = br.readLine();
	String S = s;
	String T = t;
	if(s.length() != t.length()) {
	int len = LCM(s.length(), t.length());
	while(S.length() != len) {
	S += s;
	}
	while(T.length() != len) {
	T += t;
	}
	}
	if(S.equals(T)) System.out.print(1);
	else System.out.print(0);
	}
	static int GCD(int a, int b) {
	while(b > 0) {
	int temp = a;
	a = b;
	b = temp%b;
	}
	return a;
	}
	static int LCM(int a, int b) {
	return (a*b)/GCD(a, b);
	}
	}

view raw BOJ12871.java hosted with ❤ by GitHub