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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12904?language=java

프로그래머스

 

---

문제 개요

주어진 문자열 s에서 부분 문자열 중 가장 긴 팰린드롬(앞뒤가 똑같은 문자열)의 길이를 찾아 반환하는 문제

팰린드롬이란?
팰린드롬(Palindrome)은 앞뒤를 뒤집어도 동일한 문자열을 의미한다. 예를 들어, "abcdcba"와 같은 문자열은 팰린드롬이며, "abcba", "aa", "a"도 팰린드롬에 해당

 

풀이

1. 문자열의 각 위치를 중심으로, 양쪽으로 확장하면서 팰린드롬이 되는 부분 문자열을 찾는다
2. 팰린드롬의 길이를 확인할 때, 두 가지 경우를 고려해야 합니다
   • 중심이 하나인 경우 (홀수 길이의 팰린드롬): 예를 들어 "aba".
   • 중심이 두 개인 경우 (짝수 길이의 팰린드롬): 예를 들어 "abba".

각 위치에서 팰린드롬을 확장하는 과정을 반복하여 가장 긴 팰린드롬의 길이를 찾는다

import java.util.*;
class Solution{
    public int solution(String s){
        int answer = 0;
        
        for(int i=0; i<s.length(); i++) {
            answer = Math.max(answer, palindrome(s, i, i));
            answer = Math.max(answer, palindrome(s, i, i+1));
        }
        
        return answer;
    }
    
    public int palindrome(String s, int left, int right) {
        while (true) {
            if(left<0 || right>=s.length()) break;
            if(s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            } else {
                break;
            }            
        }
        return right - left - 1;
    }
}