[Programmers] Lv3 가장 긴 펠린드롬

Programmers Lv3 가장 긴 펠린드롬

문제 링크

풀이 과정

이 문제는 투포인터 그리고 성능 최적화를 이용하기 위해 DP를 적용할 수 있는 문제다.

투포인터 풀이 과정

Two pointer
1. 시작 지점 i와 주어진 문자열 최대 길이 limit을 구한다.
2. 시작 지점 i에서부터 확인할 문자열의 길이 length 까지의 펠린드롬 여부를 확인할 함수 isPalindrome(String target, int from, int to); 을 정의한다.
3. isPalindrome 내부에서는 target[from] == target[to] 인 경우 from+1과 to-1 을 반복해서 체크하도록 한다.
4. isPalindrome 이 true 를 반환하면 최대 팰린드롬 길이를 갱신한다.

위 과정을 코드로 옮기면 아래와 같다.

import java.util.*;

class Solution
{
    private int limit = 0;

    private boolean isPalindrome(String target, int from, int to) {
        while(from <= to) {
            if(target.charAt(from) != target.charAt(to)) {
                return false;
            }
            from++;
            to--;
        }

        return true;
    }

    public int solution(String s)
    {
        limit = s.length();

        for(int length = limit ; length > 0 ; length--) {
            for(int start = 0 ; start + length <= limit ; start++) {
                if(isPalindrome(s, start, start+length-1)) {
                    return length; // 여기서는 최장 길이를 우선 탐색하기 때문에 조건이 팰린드롬이라면 곧 최장 길이의 팰린드롬이다. 따라서 리턴
                }
            }
        }

        return 0;
    }
}

메모이제이션을 이용한 최적화

1. 팰린드롬 여부를 저장할 2차원 배열 boolean dp[s.length()][s.length()] 를 생성한 뒤 false로 초기화한다.
2. dp[i][j] 는 s의 부분 문자열 substring(s, i, j) 가 팰린드롬인지 여부를 나타낸다.
2. dp[i][i] for i in range(0, s.length()) 를 전부 true 로 초기화 한다.
3. dp[i][i+1] for i in range(0, s.length() - 1) 에 대해 s[i] == s[i+1] 이라면 전부 true 로 초기화한다.
4. 이제 위에 작성한 Two Pointer 알고리즘을 수행하는데, isPalindrome(String target, int from, int to) 가
반복문을 통해 from+1, to-1 역시 Palindrome 조건을 만족하는지 확인했다면,
이젠 dp[from+1][to-1] 를 이용하여 간단히 확인할 수 있다. 
s[from] == s[to]를 만족하고 s의 부분문자열 substring(s, from+1, to-1) 이 팰린드롬이라면 substring(s, from, to) 역시 부분 문자열이기 때문

위 방식을 코드로 옮기면 아래와 같다.

import java.util.*;

class Solution
{
    public int solution(String s)
    {
        boolean[][] dp = new boolean[s.length()+1][s.length()+1];
        int answer = 1;
        int limit = s.length();

        for(int i = 0 ; i <= limit ; i++) {
            for(int j = 0 ; j <= limit ; j++) {
                dp[i][j] = false;
            }
        }

        for(int i = 0 ; i < limit ; i++) {
            dp[i][i] = true;
        }

        for(int i = 0 ; i < limit - 1 ; i++) {
            if(s.charAt(i) == s.charAt(i+1)) {
                dp[i][i+1] = true;
                answer = 2;
            }
        }

        for(int length = 3 ; length <= limit ; length++) {
            for(int start = 0; start + length <= limit ; start++) {
                int to = start + length - 1;

                if((s.charAt(start) == s.charAt(to)) && (dp[start+1][to-1])) {
                    answer = Math.max(answer, length);
                    dp[start][to] = true;
                }
            }
        }

        return answer;
    }
}