단계별로 풀어보기(문자열 알고리즘1 - 문자열 제곱)

4354번: 문자열 제곱 (acmicpc.net)

4354번: 문자열 제곱

http://boj.kr/73ebbf34281d4f89a881990fc56a6096

공유 소스 보기

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

class Main{
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String str;
		
		char[] charArr;
		
		int[] arr;
		
		int j;
        double result;
		
		while(true) {
			
			str = br.readLine();
			
			if(str.equals(".")) break;
			
			charArr = str.toCharArray();
			
			arr = new int[charArr.length];
			
			j = 0;
			
			
			for(int i = 1; i < charArr.length; i++) {
				
				while(j > 0 && charArr[j] != charArr[i]) {
					
					j = arr[j - 1];
					
				}
					
				if(charArr[j] == charArr[i]) {
					
					arr[i] = ++j;
					
				}
				
			}
			
			result = (double) charArr.length / (charArr.length - arr[charArr.length - 1]);
			
			if(charArr.length % result == 0 && result % 1 == 0) {
				
				bw.write(String.valueOf((int) result));
				
			}else {
				
				bw.write("1");
				
			}
			
			bw.newLine();
			
		}
		
		bw.close();
        
    }
    
}

---

 

 

//시간복잡도가 엉망인 코드
public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String str, compare, lastToken;
		int result;
		
		while(true) {
			
			str = br.readLine();
			
			if(str.equals(".")) break;
			
			result = 1;
			loop:
			for(int i = 1; i < str.length() / 2; i++) {
				
				compare = str.substring(0, i);
				
				lastToken = str.substring(str.length() - i,str.length());
				
				if(str.length() % compare.length() != 0 || !compare.equals(lastToken)) continue;
				
				for(int j = 1; j < str.length() / compare.length(); j++) {
					if(!compare.equals(str.substring(compare.length() * j, compare.length() * (j + 1)))) {
						break;
					}
					if(j == str.length() / compare.length() - 1) {
						result = str.length() / compare.length();
						break loop;
						
					}
				}
				
			}
			
			bw.write(String.valueOf(result));
			bw.newLine();
		}
		
		bw.close();

	}

}

일단 처음 시작에는 그냥 문자열을 증감식으로 substring 해서

 

전체 비교를 했다.

 

시간 복잡도를 줄여보려고 나름대로 조건을 걸어봤는데

 

1. 비교하는 문자열의 길이가 전체의 1/2을 넘어가면 의미가 없다.

 

2. 비교하는 문자열의 길이를 전체 문자열의 길이에 나눴을 때 나누어 떨어져야 한다.

 

3. 단순 비교가 아닌 나 자신의 길이만큼 나누어서 비교해야 한다.

 

이렇게 했는데 시간 초과 떴다...

 

그래서 문자열 비교를 어떻게 효율적으로 할 수 있을까 고민했는데

 

이걸 삽질하면서 고민할 바에는 저 코드를 살리기 위해

 

추가 조건을 찾거나

 

이미 있는 알고리즘을 분석해서 응용하기로 했다.

 

Botherahn :: [알고리즘] 실패 함수(문자열 검색 - KMP 알고리즘 관련) (tistory.com)

[알고리즘] 실패함수(문자열 검색 - KMP 알고리즘 관련)

조건을 알아보기 위해 검색 순서가

 

문자열 제곱 - > 실패 함수 순으로 가는 바람에

 

이미 답에 해당되는 부분을 보고 말았는데

 

그 부분은 실패 함수를 알면 쉽게 생각해낼 수 있는 부분이라

 

큰 문제가 없었는데

 

접미사와 접두사를 비교한다고 그 안에 있는

 

모든 문자가 조건을 만족하는가? 이게 문제였다.

 

직관적으로 생각했을 때 만족하지 않는다면

 

result가 자연수로 나오지 않겠구나라고 생각이 들었는데

 

이걸 어떻게 증명해야 할까 막막해서 데이터 여러 개 넣어보고

 

문제없어서 그냥 만족하고 넘어갔다.

 

근데 제출했을 때 실패가 나왔는데 반례를 찾아보니

 

abcdabcdabcdabc << 얘가 있었다.

 

arr.length % result == 0 처음 조건을 얘만 걸어뒀는데

 

result를 int형으로 놔서 문제가 생겼구나 하고

 

double로 바꿨는데도 문제가 생기는 거다

 

그래서 계산해보니 3.75로

 

나누어 떨어지더라,, 그래서 result가 소수이면

 

1을 출력하게 바꾸니 성공했다.