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

https://www.acmicpc.net/problem/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을 출력한다.

 

풀이

---

주어진 문자열 s 와 문자열 t 의 길이가 같으면 그대로 비교!

 

다르면 최소공배수 만큼 문자열을 붙이고 비교한다.

생각보다 간단한데,,,,,, 아이디어 생각하기가 쉽지않았다리....

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main_BOJ_12871_무한문자열 {
    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 = lcd(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);
    }

    private static int lcd(int a, int b) {
        return (a * b) / gcd(a, b);
    }

    private static int gcd(int a, int b) {
        int tmp;
        while (b > 0) {
            tmp = a % b;
            a = b;
            b = tmp;
        }

        return a;
    }
}