프로그래머스] C++ 연습문제 - 가장 긴 팰린드롬(level 3)

해당 문제는 프로그래머스 코딩테스트 연습에 있는 문제입니다.

아래 링크를 통해 풀 수 있습니다.

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

1. 문제

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

2. 조건

1. 문자열을 반대로 뒤집었을 때 동일한 문자열이 나와야 합니다.

EX) baab 를 뒤집으면 baab, abcba를 뒤집으면 abcba.

aabbcc를 뒤집으면 ccbbaa가 되므로 X.

2. 뒤집었을 때 동일한 문자열 중 가장 긴 문자열을 return.

3. 풀이

굉장히 쉬운 문제인데 한가지 유의해야 합니다.

문자열이 홀수일 때와 짝수일 경우입니다.

baab일 경우 짝수이지만 abcba일 경우 홀수입니다.

따라서 짝수일 경우와 홀수일 경우 구하는 방식이 조금 달라집니다.

짝수는 위 아래를 비교하면서 나아가면 되지만,

홀수일 경우는 문자 하나를 중심으로 둬야합니다.

저는 while문 안에 하나는 중심을 두지 않고 값이 일치하는지 구하고,

다른 하나는 중심을 두고 일치하는지 구했습니다.

그림으로 표현하자면 다음과 같습니다.

이런식으로 계산되게 구했습니다.

4. 코드

#include <iostream>

#include <string>

using namespace std;

int solution(string s){

    int answer = 1; 

    s.push_back(1);

    for(size_t i = 1; i < s.size(); i++){

        int left = i - 1, right = i + 1, count_1 = 0, count_2 = 1;

        bool f1 = false, f2 = false;

        while(left >= 0 && right < s.size()){

            

            if(s[left] == s[right - 1]) count_1 += 2;

            else f1 = true;

            if(s[left--] == s[right++]) count_2 += 2; 

            else f2= true;

            if(f1 && f2) break;       

        }

        int result = (count_1 > count_2) ? count_1 : count_2;

        answer = (result > answer) ? result : answer;

    }

    return answer;

}