[팰린드롬 문제] 프로그래머스,백준 풀이-Manacher's 알고리즘

팰린드롬 문제를 접하고 비슷한 문제들의 다양한 풀이 방법을 모아보았다.

단순히 팰린드롬인지 확인하는 문제가 아닌 문자열의 부분문자열이 팰린드롬인지, 그중 가장 긴 길이는 얼마인지 찾는 문제를 풀어보았다.

그냥 탐색이 아니라 알고리즘 적용해서 푸는건 아예 모르겠어서 여기저기 찾아보고 manacher알고리즘을 알게 되었다!

 

팰린드롬(Palindrome)이란?

abcba 처럼 양쪽이 대칭이 되는 문자열을 의미한다. 한 글자의 a 두 글자의 aa 역시 팰린드롬이다.

 

프로그래머스-가장 긴 팰린드롬

 

이 문제는 주어진 문자열의 부분 문자열 중 가장 긴 팰린드롬의 길이를 찾는 문제이다.

문자열 최대길이가 2500 이므로 넉넉하게 각 인덱스마다 탐색으로 진행하면 되겠다.

 

 

public class LongestPalindrome {

	static int[] pal;
	static int len;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		String s = "abcdcba";
	
		for(int i=s.length();i>1;i--) {//제일 긴 문자열부터
			
			for(int j=0;j+i<=s.length();j++) {//j~길이만큼
				boolean flag=true;
				
				for(int k=0;k<i/2;k++) {//대칭되는거 같은지 확인
					if(s.charAt(k+j)!=s.charAt(j + i  - k - 1)) {
						flag=false;
						break;
					}
				}
				if(flag) {
					System.out.println(i);
					return;
				}
			}
			
		}
	}
	
}

 

백준 10942 - 팰린드롬?

 

이 문제는 주어진 수열의 부분수열인 start ~end 가 펠 린드 롬인지 찾는 문제이다.

start와 end는 최대 1000000개까지 주어진다.

 

이문제의 경우 dp를 이용하여 전체 start~end의 팰린드롬 여부를 미리 구해놓고 중복으로 구해지는 부분을 최소화하여 풀 수 있다.

 

dp 배열 이용방법

 

 

package baekjoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Ex_10942 {

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		//팰린드롬?
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] arr = new int[n+1];
		boolean[][] dp = new boolean[n+1][n+1];
		for(int i=1;i<=n;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
			dp[i][i]=true;//1개짜리 팰린드롬 ->a , b ...
		}
		for(int i=1;i<=n-1;i++) { //2개짜리 팰린드롬 -> aa , bb ...
			if(arr[i]==arr[i+1])
				dp[i][i+1]=true;
		}
		for(int k=2;k<=n-1;k++) {//몇 칸 뛸지
			for(int i=1;i<=n-k;i++) {
				int j=i+k;
				if(arr[i]==arr[j]&& dp[i+1][j-1])
					dp[i][j]=true;
			}
		}
		
		int m = Integer.parseInt(br.readLine());
		while(m-- >0) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			
			if(dp[start][end]) {
				bw.append(1+"\n");
			}else {
				bw.append(0+"\n");
			}
		}
		bw.flush();
	}
	

}

 

 

백준 14444 - 가장 긴 팰린드롬 부분 문자열

 

 

이 문제 역시 위의 문제들과 같은 문제이지만 다른점이 최대 길이가 100,000이라는 것이다. 당연히 n^2으로 풀게되면 시간 초과가 나니 다른 방법으로 풀어야 하는데 이것이 Manacher's 알고리즘이다.

 

 

Manacher 알고리즘이란 ?

-문자열 배열에서 i번째 문자를 중심으로 하는 가장 긴 팰린드롬 길이를 반지름 r을 저장하여 사용한다.

-이 방법은 O(N)이라는 효율적인 시간 복잡도를 갖고 있다.

 

 

 

알고리즘 동작 방식

-i는 배열의 길이(문자열 길이)만큼 진행된다.

 

-짝수 팰린드롬 경우를 위해 #으로 패딩을 주어 진행한다.

          aa -> a를 기준으로 양옆이 같지 않음

          #a#a# ->#를 기준으로 양옆이 같아 팰린드롬으로 잘 검출됨

 

-a [] 배열에는 해당 인덱스를 중심으로 하는 가장 긴 팰린드롬의 길이를 저장한다.

          반지름 길이를 저장하는 것이지만 #으로 늘렸으므로 전체 길이가 된다.

-사용하는 변수가 2개가 있다.

          r -> 해당 인덱스까지 가장 긴 팰린드롬의 우측 끝

          p-> 해당 인덱스까지 가장 긴 팰린드롬이 중심 인덱스

 

-팰린드롬이라고 정해져 있는 인덱스에 속해있는지 검사하여 a [i]의 값을 초기화한다.

         #b#a#n#a#n#a# -> a의 경우 이미 n에 해당하는 인덱스에서 #까지가 팰린드롬에 해당한다는 것을 체크하여

         r이 #인덱스에 해당하는 8의 값을 가진다. 따라서 기본 a [a인덱스]의 초기값이 1이 된다. (코드 보고 이해)

 

-양끝이 배열에서 벗어나지 않고 && 문자가 같다 -> a [i]의 값을 늘려준다.

 

아래 출력 값을 보면 어떻게 배열이 차고 길이를 구하는지 감이 온다.

이해가 어렵다면 코드 한 줄씩 디버깅을 추천

 

i증가에 따른 a[]배열과 변수 값들

package baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Ex_14444 {
	static int[] a;
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		//가장 긴 팰린드롭 부분 문자열 manacher 알고리즘
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		String str= "";
        //짝수 문자열 위해 ex) acca -> #a#c#c#a# 확장
		for(int i=0;i<input.length();i++) {
			str += "#";
			str += input.charAt(i);
		}
		str+="#";

		a = new int[str.length()];
		manacher(str,str.length());
		int max = 0;
		for(int i : a) {
			max = Math.max(max, i);
		}
		System.out.println(max);
	}
	static void manacher(String str,int n) {
		int p = 0;//가장 긴 팰린드롬의 중심 인덱스
		int r = 0;//가장 긴 팰린드롬의 우측 끝 인덱스
        
		for(int i=0;i<n;i++) {
			
            //이미 팰린드롬이라고 정해져있는 인덱스에 속해있는지
			if(i <= r) {
				a[i] = Math.min(r-i, a[2*p-i]);
			}else {
				a[i] = 0;
			}
			
            //양끝이 인덱스가 배열에서 벗어나지 않고 && 문자가 같다면 팰린드롬에 추가 후 길이 늘려주기
			while(i-a[i]-1 >= 0 && i +a[i] + 1 < n &&  str.charAt(i - a[i] - 1) == str.charAt(i + a[i] + 1)) {
				a[i]++;
			}
			if(r<i+a[i]) {
				r = i+a[i];
				p = i;
			}
		}
	}

}

 

 

참고 사이트

www.crocus.co.kr/1075

 

이해하는데 한참 걸렸다.. 더 열심히 해야겠다 ㅎ