[백준][12871][Java] 무한 문자열

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

12871번: 무한 문자열

문제풀이

처음에는 S를 짧은 문자열이라는 가정하에 T에 맞춰 S를 증가시켜주면서 길이가 똑같아졌을 때 비교를 하였지만 'cc'와 'ccc'의 경우 앞선 가정을 무시해버린다. 그래서 두 문자열의 최소 공배수를 찾고 문자열을 늘려줘서 비교해줬다.

최소 공배수를 찾는 과정에서 97%에서 시간초과가 나는데 유클리드 호재법를 쓰게 되면서 해결이 되었다.

 

코드

import java.io.*;
import java.util.*;

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 num1 = s.length();
		int num2 = t.length();
		int result = 0;

		// 최소 공배수 구하기
		int min = (num1 * num2) / gcd(Math.max(num1, num2), Math.min(num1, num2));

		// 최소 공배수의 길이가 되도록 s 더하기
		String tmp = s;
		while (true) {
			if (s.length() == min)
				break;

			s += tmp;
		}

		// 최소 공배수의 길이가 되도록 t 더하기
		tmp = t;
		while (true) {
			if (t.length() == min)
				break;
			t += tmp;
		}
		
		if(s.equals(t)) result =1;
		System.out.println(result);
	}
	
	static int gcd(int max, int min) {	
		while(min!=0) {
			int remainder = max%min;
			max =min;
			min = remainder;
		}
		
		return max;
	}

}