5-moran991231.md

5. Longest Palindromic Substring

Solution 1

시간복잡도 : O(N^2)

Nested for loop :O(N)*O(N)

알고리즘 : Brute force

풀이 설명 :

주어진 문자열 s의 부분 문자열 중에서 가장 긴 회문을 구하라.

문자열s길이를 N이라고 할 때, s의 부분문자열의 경우의 수는 N*(N-1)/2+N이다. (N은 시작인덱스와 끝인덱스가 같아서 부분문자열의 길이가 1인 경우)

s에서 부분문자열의 시작인덱스와 끝 인덱스를 고르는 경우와 같다.

이는 아래와같은 2중 for문으로 작성할 수 있다.

for(start = 0; start < N; start++)
	for(end = start; end < N; end++)
		...(부분문자열 회문검사 코드)...

그러나 위와 같이 작성하면 불필요한 검사를 하게 될 뿐더러 시간초과가 발생한다. (맙소사!)

개선방안:

문제를 다시 읽어보면, '문자열 s의 부분 문자열 중에서 "가장 긴" 회문을 구하라.'라고 적혀있다. 가장 긴 회문의 경우만 구하면 되므로 부분문자열을 검사하면서 회문이 가장 긴 길이를 longest_len에저장해 놓고, 다음에 부분문자열을 고를 때 longest_len보다 길이가 긴 녀석만 검사한다.

for(start=0; start < N; start++)
	for(end = start + longest_len; end < N; end++)
		...

Tip:

연산속도를 올려보고자(?) class의 필드와 메소드를 모두 static으로 변경하였는데 오답이 나왔다! 테스트 코드를 실행시키고 연산을 반복하나보다. 필드 변수들을 지역변수로 바꾸거나 함수 실행시 초기화 해주거나 static하지 않게 만들자.

DP를 이용한 방법도 존재한다.

소스코드 :

class Solution {
	 int longest_len = 0;
	 int longest_s, longest_e;

	public  void calc(String str, int start, int end) {
		int s, e;
		for (s = start, e = end; s <= e; s++, e--)
			if (str.charAt(s) != str.charAt(e))
				return;
		if (longest_len < (end - start + 1)) {
			longest_len = (end - start + 1);
			longest_s = start;
			longest_e = end;
		}
	}

	public  String longestPalindrome(String s) {
		int len = s.length();
		for (int start = 0; start < len; start++) {
			for (int end = start+longest_len; end < len; end++) {
				calc(s, start, end);
			}
		}
		System.out.println(longest_len);
		return s.substring(longest_s, longest_e+1);
	}
}