[프로그래머스] 다이나믹 프로그래밍(DP) - 가장 긴 팰린드롬 (Java)

프로그래머스 Level 3 다이나믹 프로그래밍(DP) - 가장 긴 팰린드롬 (자바)

 

 

출처

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는 알파벳 소문자로만 구성

 

 

 

 

 

입출력 예

입출력 예 1

 

 

 

접근 방법

DP문제인데 도저히 접근방법을 모르겠어서 빡구현했다...(DP로도 풀어야 하는데 방법을 도저히 모르겠다..)

큰 카테고리는 팰린드롬이 가능하게 하는 가운데 대칭 문자의 개수가 홀수개인지 짝수개인지 비교 후 연산하는 것이다.

 

1. 홀수개인 경우에는 i-1번째 문자와 i+1 문자가 같은 경우이다. i-1번째 문자를 사용하기 위해서는 i가 1 이상이어야 하므로 i>0 조건을 추가했다.

 

2. 짝수개인 경우에는 i번째 문자와 i+1 문자가 같은 경우다.

 

3. 각각 경우에 따라 시작하는 left, right에 순서를 넣어놓고, 해당 순서의 문자가 같아야 left--, right++하며 전체 길이를 계산하도록 한다. (이 연산은 배열의 크기를 넘어가면 안 되므로 left>=0, right <=s.length()-1 까지만 가능하다.) 

 

4. 연산 후에 짝수개의 길이가 긴 경우는 *2만 하면 되지만, 홀수개의 길이가 긴 경우는 *2 +1 하여 결과를 출력한다.

 

 

 

내 코드

class Solution
{
    private static int left, right, cnt;
    public int solution(String s)
    {
        int answer = 0;
        
        //대칭수 개수가 홀수, 짝수 일 때 나눠서 비교
        //위 조건 충족시 왼쪽, 오른쪽 수가 같으면 --, ++ 해주기
        //--, ++ 연산 후 둘이 같지 않으면 while문 빠져나오기
        
        int oddCnt = 0;
        int evenCnt = 0;
        
        for (int i=0; i<s.length()-1; i++) {
            left = right = cnt = 0;
            
            if (i>0 && s.charAt(i-1) == s.charAt(i+1)) {
                //홀수
                left = i-1;
                right = i+1;
                cnt = 0;
                
                checkPelin(s);
                
                if (oddCnt < cnt) oddCnt = cnt;
            }
            if (s.charAt(i) == s.charAt(i+1)) {
                //짝수
                left = i;
                right = i+1;
                cnt = 0;
                
                checkPelin(s);
                
                if (evenCnt < cnt) evenCnt = cnt;
            }
        }
        
        if (evenCnt > oddCnt) {
            answer = evenCnt*2;
        } else {
            answer = oddCnt*2 + 1;
        }

        return answer;
    }//main
    
    private static void checkPelin(String s) {

        while (left >= 0 && right <= s.length()-1) {
            if (s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
                cnt++;
            } else {
                break;
            }
        }
        
    }//checkPelin
}

 

 

고려할 점

1. 문자열 문제....

2. 배열 길이까지 계속해서 계산을 하기 위한 자동화 방법을 고민할 것