[프로그래머스(Programmers)][자바(java)] (Lv3) 가장 긴 팰린드롬

 

programmers.co.kr/learn/courses/30/lessons/12904

코딩테스트 연습 - 가장 긴 팰린드롬

 

 

문제 설명

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 abcdcba이면 7을 return하고 abacde이면 3을 return합니다.

 

제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

 

입출력 예

s	answer
abcdcba	7
abacde	3

입출력 예 설명

입출력 예 #1
4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

입출력 예 #2
2번째자리 'b'를 기준으로 aba가 팰린드롬이 되므로 3을 return합니다.

 

 

문제 풀이

 

▶  이중 loop

public class Solution {
	
	public int solution( String s ) {
        int len = s.length();
        if( len == 1 )
        	return len;
       	int start, end, left, right, p, p_max = 0;	// p : palindrome
        outer:
        for( start = 0; start < len; start++ ) {
        	inner:
        	for( end = len-1; end >= start; end-- ) {
        		left = start;
        		right = end;
        		while( left <= right ) {
        			if( s.charAt( left ) == s.charAt( right ) ) {
        				left++; 
        				right--;
        			}
        			else	/* 's' 's sub string ( start~end ) is not palindrome */
        				continue inner;
        		}
        		/* 's' 's sub string ( start~end ) is palindrome */
        		p = end - start + 1;	/* get current p len */
        		p_max = p_max < p ? p : p_max;
        		if( p_max == len )
        			return p_max;
				continue outer;
        	}
        }
        return p_max;
    }
}

* 투 포인터 (?)

- start, end, left, right에는 문자열 s의 인덱스 값을 담는다.
- 문자열 s를 이중 for문으로 탐색 ( outer => start, inner => end )
- start는 앞에서부터, end는 뒤에서 부터. ( 가장 긴 팰린드롬을 구해야 하고 탐색 횟수를 줄이기 위해 )
- start와 end를 각각 left, right에 넣은 후 투 포인터로 양 끝에서부터 가운데로 탐색하며 두 문자가 같은지 비교한다.
- 하나라도 틀리면 팰린드롬이 아니므로 end를 1 빼고 inner loop를 다시 반복
- 모두 같으면 팰린드롬이며, end-start+1 하여 현재 p를 구한 후 p_max와 비교하여 p_max를 갱신함
- 현재 start에서 팰린드롬을 구했으면 start+1 하여 outer loop를 다시 반복

 

▶  마나허( Manacher ) 알고리즘

import java.util.Scanner;

public class Solution {
	
	public static int[] manachers( char c[], int l, int a[] ) {
		int r = -1, p = -1, i;
		for( i = 0; i < l-1; i++ ) {
			a[i] = i <= r ? Math.min( a[2*p-i], r-i ) : 0;
			while( i-a[i]-1 >= 0 && i+a[i]+1 < l && c[i-a[i]-1] == c[i+a[i]+1] )
				a[i]++;
			if( r < i + a[i] ) {
				r = i + a[i];
				p = i;
			}
		}
		return a;
	}

	public static int solution( String s ) {
		
		int l = s.length(), i;
		StringBuilder sb = new StringBuilder();
		sb.append( "#" );
		for( i = 0; i < l; i++ )
			sb.append( s.charAt(i) + "#" );
		s = sb.toString();
		l = s.length();
		char c[] = s.toCharArray();

		int len = 0;
		int a[] = new int[l];
		a = manachers( c, l, a );
		for( int ll : a )
			if( len < ll )
				len = ll;
		
		return len;

	}
}

( 참고 : algospot.com/wiki/read/Manacher's_algorithm )