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

문제 설명

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 abcdcba이면 7을 return하고 abacde이면 3을 return합니다.

 

제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

---

C++ 풀이

#include <string>
using namespace std;

int longest;
string word; int wordsize;

void oddlengthCheck(int position) { //홀수 길이의 팰린드롬이라 가정했을때 길이 구하기
	int count = 1;
	for (int i = 1; i <= wordsize; i++) {
		if ((position - i < 0) || (position + i >= wordsize))
			break;
		if (word[position - i] == word[position + i])
			count += 2;
		else
			break;
	}
	if (count > longest)
		longest = count;
}
void evenlengthCheck(int position) { //짝수 길이의 팰린드롬이라 가정했을때 길이 구하기
	int count = 0;
	for (int i = 0; i < wordsize; i++) {
		if ((position - i < 0) || (position + i >= wordsize - 1))
			break;
		if (word[position - i] == word[position + i + 1])
			count += 2;
		else
			break;
	}
	if (count > longest)
		longest = count;
}

int solution(string s)
{
	longest = 1;
	word = s;
	wordsize = s.length();
	for (int i = 0; i < s.length(); i++) {
		oddlengthCheck(i);
		evenlengthCheck(i);
	}
	return longest;
}

주어진 단어의 모든 글자에 대해서, 해당 글자가 팰린드롬의 기준(중앙)이라 가정했을 때의 팰린드롬 길이값을 구한다.

팰린드롬의 글자 수가 홀수 / 짝수 일 때를 나눠서 구했다.

 

 

 

 

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/12904

코딩테스트 연습 - 가장 긴 팰린드롬 | 프로그래머스