[Algorithm] 백준 문자열 문제 - 무한 문자열(12871) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 문자열 문제 - 무한 문자열 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/12871

12871번: 무한 문자열

 

1. 풀이 소스 

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        String str1 = br.readLine();
        String str2 = br.readLine();
        
        int gcd = getGCD(str1.length(), str2.length()); // 최대 공약수 찾기
        if (gcd == 1) gcd = str1.length() * str2.length(); // 1이라면 최소 공배수는 두 문자열 길이의 곱
        else gcd = str1.length() * (str2.length() / gcd); // 1이 아니라면, 문자열 길이 * 문자열 길이 / 최대 공약수

        str1 = repeat(str1, gcd); // 문자열 반복
        str2 = repeat(str2, gcd);

        if (str1.equals(str2)) sb.append(1);
        else sb.append(0);
        
        System.out.print(sb);
    }

    // 유클리드 호재법
    static int getGCD(int x, int y) {
        if (y == 0) return x;
        return getGCD(y, x % y);
    }

    // 최소 공배수 개수만큼 문자열 증가
    static String repeat(String str, int lcm) {
        String repeat = str;
        while (str.length() < lcm) {
            str += repeat;
        }
        return str;
    }
}

 

2. 풀이 중점 사항

 

최소 공배수만큼 문자열을 반복한 후, 두 문자열을 비교하는 방법을 사용하였습니다.

중점 사항은 최대 공약수를 구하는 알고리즘입니다. 유클리드 호재법을 활용하여 재귀로 문제를 해결할 수 있습니다.

 

static int getGCD(int x, int y) {
    if (y == 0) return x;
    return getGCD(y, x % y);
}

 

나머지 풀이는 주석으로 대체하였습니다 감사합니다.!