문제 이해

입력

• string s
  • 1≤ s ≤ 2,500

출력

• 가장 긴 팰린드롬의 길이
  • 팰린드롬 → 앞뒤를 뒤집어도 똑같은 문자열

문제 풀이

• O(N^2)까지는 시간 복잡도 여유 있음

1. 구현
   1. 길이가 1이면 → 1
   2. 길이가 2이면
      1. 두 문자가 다르면 1
      2. 두 문자가 같으면 2
   3. s의 각 문자를 순회하면서 팰린드롬 체크
      1. 이때 홀/짝으로 구분

→ 결과: 97/100

1. 투포인터
   1. left, right 포인터를 이용해서 팰린드롬 체크

1. 구현(97/100)

   #include <iostream>
   #include <string>
   using namespace std;
   int solution(string s)
   {
       int answer=1;
       int n = s.size();
       
       if (n==1) {
           return answer;
       }
       
       if (n==2) {
           return s[0]==s[1] ? 2 : 1;
       }
       
       for (int i=1; i<n-1; i++) {
           int p=0;
           // 홀수 팰린드롬
           for (int j=1; i-j>=0 && i+j<n; j++) {
               if (s[i-j]==s[i+j]) p++;
               else break;
           }
           answer=max(2 * p + 1, answer);
           
           p=0;
           // 짝수 팰린드롬
           for (int j=0; i-j>=0 && i+j+1<n; j++) {
               if (s[i-j]==s[i+j+1]) p++;
               else break;
           }
           answer=max(2 * p, answer);
       }
   
       return answer;
   }
   
   

2. 투포인터

   #include <iostream>
   #include <string>
   #include <algorithm>
   
   using namespace std;
   
   // 결과를 저장할 전역변수 answer
   int answer = 0;
   
   void isPellin(string s, int left, int right) {
   	int ans = 0;
   
   	while (left >= 0 && right < s.size()) {
   		if (s[left] != s[right]) {
   			break;
   		}
   		left--;
   		right++;
   	}
   
   	ans = right - left-1;
   
   	answer = max(answer, ans);
   }
   
   int solution(string s)
   {
   
   	for (int i = 0; i<s.size(); i++) {
   		isPellin(s, i, i+1); //짝수 케이스
   		isPellin(s, i, i); //홀수 케이스
   	}
       
   	return answer;
   }