[D3] 무한 문자열 - 15758 (Java)

 

문제 요약

문자열 S에 대해, f(S)를 S를 무한히 반복해서 얻은 문자열이라고 정의하자. 예를 들어 f(“abcd”) = “abcdabcdabcdabcd…”이다.

S≠T이라도 f(S)=f(T) 일 수 있다. 예를 들어 S = “ababab”, T = “abab”라면 f(S)와 f(T) 모두 “ababababababab…”이다.

두 개의 문자열 S와 T가 주어질 때, f(S)=f(T)인지의 여부를 구하는 프로그램을 작성하라.

---

문제 분석

두 문자열 길이의 최소공배수를 구한 후 각 문자열을 그 길이만큼 확장하고 두 문자열이 같은지 비교한다.

---

코드

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

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int t = 1; t <= T; t++){
            sb.append("#").append(t).append(" ");
            st = new StringTokenizer(br.readLine());
            String a = st.nextToken();
            String b = st.nextToken();
            if(a.length() == b.length()){
                sb.append(a.equals(b) ? "yes": "no").append("\n");
                continue;
            }
            // 두 단어 길이의 최소공배수를 구함
            int lcmLength = lcm(a.length(), b.length());
            String extendedA = extendString(a, lcmLength);
            String extendedB = extendString(b, lcmLength);
            sb.append(extendedA.equals(extendedB) ? "yes": "no").append("\n");
        }
        sb.deleteCharAt(sb.length()-1);
        System.out.println(sb.toString());
    }
    // 문자열 s를 길이가 최소공배수 n이 될 때까지 반복
    private static String extendString(String s, int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(s.charAt(i % s.length()));
        }
        return sb.toString();
    }

    // a,b의 최소공배수 
    private static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

    // a,b의 최대공약수
    private static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

---

정리

개선할 점

최대공약수, 최소공배수 구하는 로직을 또 까먹었다.

---