[Algorithm/Java] 백준 12871번 - 무한 문자열

---

https://www.acmicpc.net/problem/12871

---

🔍 문제 풀이

풀이 방법

최소공배수 길이까지 확장해서 전체를 비교하는 문제이다.

처음엔 최소공배수 대신 최소 길이 (min) 까지만 비교했다.

하지만 s = "ab", t = "aba"와 같은 경우 반례가 존재했다.

따라서 LCM(최소공배수)를 통해 두 문자열의 "공통 주기 길이"를 찾아야 했다.

lcm / lenS를 통해 주기 길이를 만들기 위해 몇 번 반복해야 하는지 계산했다.

💻 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s = br.readLine();
        String t = br.readLine();

        int lenS = s.length();
        int lenT = t.length();

        int lcm = lenS * lenT / gcd(lenS, lenT); // 최대공약수

        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();

        for(int i=0; i<lcm / lenS; i++) sb1.append(s); // s를 LCM 길이까지
        for(int i=0; i<lcm / lenT; i++) sb2.append(t); // t를 LCM 길이까지

        if(sb1.toString().equals(sb2.toString())) System.out.println(1);
        else System.out.println(0);
    }

    // 최대공약수
    static int gcd(int a, int b) {
        while(b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}