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

---

문제

---

풀이

해당 문제는 인덱스 접근을 통해서 풀었다. 전체 문자열을 반복하면서 패린드롬을 구하는 포인터를 다르게 하면서 홀수인 경우와 짝수인 경우의 팰린드롬을 나눠서 구했고  최대값을 저장했다.

    for(int i = 0; i < s.size(); ++i)
    {
        int odd = isPalindrome(s, i, i);
        int even = isPalindrome(s, i - 1, i);
        int ismax = max(answer, odd);
        answer = max(ismax, even);
    }

포인터로부터 left는 감소 right는 증가시켜나가며 문자열이 같은지 확인했다.

문자열의 길이는 right - left -1 이다. ex) 7 - (-1) -1

int isPalindrome(string s, int left, int right)
{
    while(left >= 0 && right < s.size())
    {
        if(s[left] != s[right]) break;
        --left;
        ++right;
    }
    return right - left - 1;
}

이렇게 구한 팰린드롬을 odd 일 때와 even일 때 최대값을 저장했다.

        int odd = isPalindrome(s, i, i);
        int even = isPalindrome(s, i - 1, i);
        int ismax = max(answer, odd);
        answer = max(ismax, even);

---

 

접근 방법

 

위의 그림과 같이, 포인터를 움직여가며 left 와 right의 글자가 동일한지 확인한다. 비교하는 글자가 하나라도 다를 경우 palindrome(팰린드롬) 형태가 아니라 판단하고, 포인터를 옮기기 전의 글자 수 중 가장 긴 글자를 찾으면 된다.

 

해당 문제에서 핵심은 펠린드롬을 찾는 방법을 구현하는 것과 홀수와 짝수 케이스를 구별해 판단할 수 있는가이다.

 

펠린드롬을 찾는 방법을 구현하는 것을 못했다면 아래의 소스코드를 보고 이해하도록 하자. isPalindrome() 함수가 팰린드롬을 검사하는 함수이다. 해당 함수는 팰린드롬을 검사하고, 만약 팰린드롬이 아니면 전의 글자 수를 비교하도록 한다.

(모르면 하는 방법의 코드를 외우도록하자!)

홀수와 짝수 케이스를 구별하는 부분이 중요하다. 보통 팰린드롬을 떠올려보면, 가운데 꼭지가 있고 양 옆이 같으면 된다. 라고 떠올리기 쉽다.

 

예를들면, "토마토"와 같이 "마"를 기준으로 "토"라는 글자가 동일하니 팰린드롬이다 라고 생각한다.

 

하지만 "토토"도 마찬가지로 팰린드롬이다. (본인은 이걸생각하지 못했다)

 

따라서, 홀수와 짝수의 경우를 나눠 팰린드롬을 구한 후, 둘 중 큰 값을 팰린드롬 중 가장 긴 팰린드롬이라고 정답화했다.

---

소스코드

#include <iostream>
#include <string>
using namespace std;

int isPalindrome(string s, int left, int right)
{
    while(left >= 0 && right < s.size())
    {
        if(s[left] != s[right]) break;
        --left;
        ++right;
    }
    
    return right - left - 1;
}

int solution(string s)
{
    int answer=0;
    for(int i = 0; i < s.size(); ++i)
    {
        int odd = isPalindrome(s, i, i);
        int even = isPalindrome(s, i - 1, i);
        int ismax = max(answer, odd);
        answer = max(ismax, even);
    }
    return answer;
}