백준 1701 cubeditor

cubeditor문제 링크: https://www.acmicpc.net/problem/1701

1701번: Cubeditor

 

cubeditor는 주어진 문자열에서 두번이상 나오는 부분문자열중에 가장긴 문자열의 길이를 구하는 문제였습니다.

 

어제 업로드한 KMP알고리즘을 사용하면 어렵지 않게 풀 수 있을줄 알았는데 센스를 필요로 하더라구요;;

센스가 없는 저는 찔끔 오래 걸렸습니다;;

 

무엇보다도 시간 초과랑 메모리 초과가 발목을 너무 잡더라구요

시간초과가 나서 이미 비교한 문자열은 비교하지 않으려고 set이나 map을 사용해서 contain함수를 썼더니 메모리가 초과나고 hashmap을 삭제하면 시간 초과가 났습니다.

 

그래서 어떻게 풀어야 될지 한참 고민하다 나온 아이디어가

longest라는 변수를 놓고 가장긴 pattern을 넣어준뒤에 다음에 비교할 pattern의 길이가 longest보다 작다면 비교할 필요가 없으므로 continue로 다음 pattern을 비교하게 만들어줬습니다.

 

또 'acabbaaaa'에서 'ac'라는 문자열은 한번밖에 안들어가므로 'aca', 'acab'등 'ac'이후에 나오는 문자열은 한번밖에 나올수 없다는것을 알고 특정 문자열이 한번밖에 안들어가면 이후 문자열은 비교할 필요가 없다는걸 알았습니다.

 

위에 두 조건을 찾는 문제인거 같더라구요.

아래는 Cubeditor의 소스코드 입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Cubeditor {
	static List<Integer> list = new ArrayList();
	static StringBuilder pattern = new StringBuilder();
	static int[] pi;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String input = br.readLine();
		pi = new int[input.length()];
		System.out.println(KMP(input));

	}

	static int[] Pi(StringBuilder pattern) {
		Arrays.fill(pi, 0);

		int j = 0;

		for (int i = 1; i < pattern.length(); i++) {

			while (j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
				j = pi[j - 1];
			}

			if (pattern.charAt(i) == pattern.charAt(j)) {
				pi[i] = ++j;
			}

		}

		return pi;
	}

	static int KMP(String origin) {
		int longest = 0;

		int size = origin.length();
		for (int i = 0; i < size; i++) {

			pattern.setLength(0);
			pattern.append(origin.charAt(i));
			for (int a = i + 1; a < size; a++) {

				int result = 0;

				pattern.append(origin.charAt(a));

				//longest보다 pattern이 작다면 볼필요가 없음
				if (longest > pattern.length()) {
					continue;
				}

				int[] tempPi = Pi(pattern);
				int j = 0;

				for (int k = 0; k < origin.length(); k++) {

					while (j > 0 && origin.charAt(k) != pattern.charAt(j)) {
						j = tempPi[j - 1];
					}

					if (origin.charAt(k) == pattern.charAt(j)) {
						if (j == pattern.length() - 1) {
							result++;
							j = tempPi[j];
						} else {
							j++;
						}
					}
				}

				if (result >= 2) {
					longest = Math.max(longest, pattern.length());
				} else {// result가 2보다 작다는것은 이후에 나올 pattern역시 1번 이하로 origin에 들어간다는 의미이므로 볼 필요가 없음
					break;
				}
			}
		}
		return longest;
	}

}