[BOJ-12871] 무한문자열 -Java

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

12871번: 무한 문자열

package algo;

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

public class 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();
		
		StringBuilder ss=new StringBuilder(s);
		StringBuilder tt=new StringBuilder(t);
		
		int sLen=s.length();
		int tLen=t.length();
		
		int lcm=(sLen*tLen)/gcd(Math.max(sLen, tLen),Math.min(sLen, tLen));
		
		for(int i=0; i<lcm/sLen-1; i++) {
			ss.append(s);
		}
		for(int i=0; i<lcm/tLen-1; i++) {
			tt.append(t);
		}
		
		int result= (ss.toString().equals(tt.toString())) ? 1:0;
		System.out.println(result);
		
	}

	private static int gcd(int max, int min) {
		
		while(min!=0) {
			int remainder=max%min;
			max=min;
			min=remainder;
		}
		return max;
	}

}

소요시간 : 15분

 

로직을 살펴보면

 

1. s의 길이와 t의 길이에 대해 최소공배수를 구한다 (유클리드 호제법 이용)

2. 최소공배수/자신의 길이 만큼 for문을 통해 s, t 의 길이를 최소공배수가 될 때까지 더해준다.

 

유클리드 호제법을 모르신다면 제 블로그에 잘 정리되어 있습니닿ㅎ

dkwjdi.tistory.com/121

유클리드 호제법(최소공약수, 최대공배수 구하기)

 

끝~~