[Algorithm] ๐Ÿ”‹๋ฐฑ์ค€ 4354 ๋ฌธ์ž์—ด ์ œ๊ณฑ

HaJingJingยท2021๋…„ 7์›” 6์ผ
0

Algorithm

๋ชฉ๋ก ๋ณด๊ธฐ
93/119

0. ๋ฌธ์ œ

์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋กœ ์ด๋ฃจ์–ด์ง„ ๋‘ ๋ฌธ์ž์—ด a์™€ b๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ab๋Š” ๋‘ ๋ฌธ์ž์—ด์„ ์ด์–ด๋ถ™์ด๋Š” ๊ฒƒ์„ ๋œปํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, a="abc", b="def"์ผ ๋•Œ, ab="abcdef"์ด๋‹ค.

์ด๋Ÿฌํ•œ ์ด์–ด ๋ถ™์ด๋Š” ๊ฒƒ์„ ๊ณฑ์…ˆ์œผ๋กœ ์ƒ๊ฐํ•œ๋‹ค๋ฉด, ์Œ์ด ์•„๋‹Œ ์ •์ˆ˜์˜ ์ œ๊ณฑ๋„ ์ •์˜ํ•  ์ˆ˜ ์žˆ๋‹ค.

a^0 = "" (๋นˆ ๋ฌธ์ž์—ด)
a^(n+1) = a*(a^n)
๋ฌธ์ž์—ด s๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์–ด๋–ค ๋ฌธ์ž์—ด a์— ๋Œ€ํ•ด์„œ s=a^n์„ ๋งŒ์กฑํ•˜๋Š” ๊ฐ€์žฅ ํฐ n์„ ์ฐพ๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ
์ž…๋ ฅ์€ 10๊ฐœ ์ดํ•˜์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ๊ฐ๊ฐ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” s๋ฅผ ํฌํ•จํ•œ ํ•œ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. s์˜ ๊ธธ์ด๋Š” ์ ์–ด๋„ 1์ด๋ฉฐ, ๋ฐฑ๋งŒ๊ธ€์ž๋ฅผ ๋„˜์ง€ ์•Š๋Š”๋‹ค. ๋งˆ์ง€๋ง‰ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๋‹ค์Œ ์ค„์€ ๋งˆ์นจํ‘œ์ด๋‹ค.

์ถœ๋ ฅ
๊ฐ๊ฐ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์— ๋Œ€ํ•ด, s=a^n์„ ๋งŒ์กฑํ•˜๋Š” ๊ฐ€์žฅ ํฐ n์„ ์ฐพ์€ ๋’ค ์ถœ๋ ฅํ•œ๋‹ค.

1. ์•„์ด๋””์–ด

๐Ÿ’ก ์‹คํŒจ ํ•จ์ˆ˜ ์ด์šฉํ•˜์—ฌ ๋ฐ˜๋ณต๋˜๋Š” ๋ฌธ์ž์—ด์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•จ
๐Ÿ’ก ๋ฐ˜๋ณต๋˜์ง€ ์•Š์œผ๋ฉด 1์„ ์ถœ๋ ฅํ•˜๊ณ , ๋ฐ˜๋ณต๋˜๋Š” ๋ฌธ์ž์—ด์ด๋ผ๋ฉด ๋ฐ˜๋ณต๋˜๋Š” ์ตœ์†Œ ๋ฌธ์ž์—ด์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•จ

2. ํ•ต์‹ฌ ํ’€์ด

  1. ์‹คํŒจ ํ•จ์ˆ˜ ์ด์šฉํ•˜์—ฌ ๋ฐ˜๋ณต๋˜๋Š” ๋ฌธ์ž์—ด์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•จ
static void getPi(String pattern) {
	char[] p = pattern.toCharArray();
		
	int j = 0;
	for(int i=1; i<p.length; i++) {
		while(j>0 && p[i] != p[j]) {
			j = pi[j-1];
		}
			
		if(p[i] == p[j]) {
			pi[i] = ++j;
		}
	}
}
  1. ๋ฐ˜๋ณต๋˜์ง€ ์•Š์œผ๋ฉด 1์„ ์ถœ๋ ฅํ•˜๊ณ , ๋ฐ˜๋ณต๋˜๋Š” ๋ฌธ์ž์—ด์ด๋ผ๋ฉด ๋ฐ˜๋ณต๋˜๋Š” ์ตœ์†Œ ๋ฌธ์ž์—ด์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•จ
int last = pi[len-1];
			
if(len%(len-last) != 0)
	System.out.println(1);
else
	System.out.println(len / (len - last));

3. ์ฝ”๋“œ

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Imple_16 {
	static int[] pi;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		while(true) {
			String s = br.readLine();
			
			if(s.equals("."))
				return;
			
			int len = s.length();
			pi = new int[len];
			
			getPi(s);
			
			int last = pi[len-1];
			
			if(len%(len-last) != 0)
				System.out.println(1);
			else
				System.out.println(len / (len - last));
		}
	}
	
	static void getPi(String pattern) {
		char[] p = pattern.toCharArray();
		
		int j = 0;
		for(int i=1; i<p.length; i++) {
			while(j>0 && p[i] != p[j]) {
				j = pi[j-1];
			}
			
			if(p[i] == p[j]) {
				pi[i] = ++j;
			}
		}
	}

}

4. ๊ฒฐ๊ณผ

์„ฑ๊ณตโœจ

profile
๐ŸŒฑ์ดˆ๋ณด ๊ฐœ๋ฐœ์ž๐ŸŒฑ

0๊ฐœ์˜ ๋Œ“๊ธ€