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

[문제 설명]

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(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합니다.

 

 

[문제 접근 방법] 

처음에는 BOJ에서 봤던 기억때문에 DP로 풀어야하나 생각을 했었다. 

그러나 모든 Substring에 대해서 팰린드롬을 구하더라도 시간초과에 걸리지 않을 것 같아서 그냥 구하기로 했다. 

(프로그래머스의 시간초과는 얼마인지 잘 모르겠는게 함정,, 1초라고 생각하고 있다.)

 

아무튼 이문제를 크게 두가지로 나누면

 

1. Substring의 가장 긴 팰린드롬을 어떻게 구할 것인가

 

2. Substring이 홀수와 짝수 처리는 어떻게 할 것인가

 

이렇게 두가지로 생각할 수 있다. 

 

1. 팰린드롬을 어떻게 구할 것인가

-> 원래 String에서 인덱스를 하나씩 지나가면서 탐색을 할 것인데,

각각의 인덱스가 Substring의 중앙이라고 생각을 하고 양쪽으로 뻗어나가면서 가장 긴 팰린드롬을 찾는 것이다. 

 

2. Substring이 홀수와 짝수 처리는 어떻게 할 것인가

->  홀수와 짝수를 나눠서 처리했는데 홀수는 최소 1개의 팰린드롬이 되고

짝수는 0개의 팰린드롬으로 시작을 하기 때문에 나눠서 해결했다.

 

아래의 코드를 보면서 이해하면 된다. 

 

[Solution] - JAVA code

class Solution
{
    public int solution(String s)
    {
        int answer = 1; 
        for(int i = 0; i< s.length()-1; i++) {
            int oddSol = oddSolution(i, s.length(), s);
            int evenSol = evenSolution(i, s.length(), s);

            if(answer < oddSol)
                answer = oddSol;
            if(answer < evenSol)
                answer = evenSol;
                                    
        }
        return answer;
    }
    /*********************************************************
    *	홀수 팰린드롬
    *    
    *   pos를 기준으로 좌우로 한칸씩 가면서
    *   팰린드롬을 체크해주고 가장 길게 될때
    *   길이를 리턴한다. 
    *    
    *********************************************************/
    public static int oddSolution(int pos, int length, String s) {
        int maxCount = 1;
        for(int i = 1; i<= length/2; i++) {
            if(pos-i < 0 || pos+i >= length) {
                break;
            }
            if(s.charAt(pos-i) == s.charAt(pos+i)) {
                maxCount +=2;
            }else {
                break;
            }
        }
        return maxCount;
    }
    
     /*********************************************************
     *	 짝수 팰린드롬
     *   
     *   pos와 pos+1이 같은지를 먼저 체크해서 
     *   같을때를 기준으로 좌우로 한칸씩 가면서
     *   팰린드롬을 체크해주고 가장 길게 될때
     *   길이를 리턴한다. 
     *   
    ***********************************************************/
    public static int evenSolution(int pos, int length, String s) {
        int maxCount = 0;
        if(s.charAt(pos) == s.charAt(pos+1)) {
            maxCount = 2;
            for(int i = 1; i<= length/2; i++) {
            
                if(pos-i < 0 || pos+1+i >= length) {
                    break;
                }
                if(s.charAt(pos-i) == s.charAt(pos+1+i)) {
                    maxCount +=2;
                }else {
                    break;
                }
            }
        }
        return maxCount; 
        
    }
}