20240304_가장 긴 팰린드롬(프로그래머스)

오늘의 TIL은 가장 긴 팰린드롬이라는 프로그래머스의 문제에 대한 내용이다.

 

문제 링크

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

프로그래머스

 

문제 설명

팰린드롬(Palindrome - 회문)이란 앞뒤를 뒤집어도 똑같은 문자열을 말한다.

문자열 s가 주어질 때, s의 부분문자열(Substring) 중에서 가장 긴 팰린드롬의 길이를 return하시오.

예를 들어, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return하시오.

 

 

제한 조건

문자열 s의 길이 : 2,500 이하의 자연수

문자열 s는 알파벳 소문자로만 구성.

 

 

해결 방안

중앙확장기법(Center Expansion Method) 사용.

중앙확장기법이란 팰린드롬 문제에서 사용되는 기법으로 문자열의 각 문자를 중심으로 팰린드롬이 될 수 있는

부분 문자열을 확장하며 검사하는 기법이다.

 

 

통과한 답안

using System;

public class Solution {
    public int solution(string s) {
        int answer = 0;

        answer = Plaindrome(s).Length;

        return answer;
    }
    public static string Plaindrome(string s)
    {
        if (string.IsNullOrEmpty(s))
        {
            return "";
        }

        int start = 0;
        int end = 0;

        for (int i = 0; i < s.Length; i++)
        {
            int length1 = CenterNum(s, i, i);
            int length2 = CenterNum(s, i, i + 1);
            int length = Math.Max(length1, length2);
            if (length > end - start)
            {
                start = i - (length - 1) / 2;
                end = i + length / 2;                    
            }
        }

        return s.Substring(start, end - start + 1);
    }

    public static int CenterNum(string s, int left, int right)
    {
        while (left >= 0 && right < s.Length && s[left] == s[right])
        {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

 

 

팰린드롬을 만족하는 길이 찾기(CenterNum)

public static int CenterNum(string s, int left, int right)
{
    while (left >= 0 && right < s.Length && s[left] == s[right])
    {
        left--;
        right++;
    }
    return right - left - 1;
}

 

CenterNum이라는 함수를 만들어서 좌우가 같은 문자들이 연속되는 길이를 찾는다.

 

 

가장 긴 Palindrome 만들기

public static string Plaindrome(string s)
{
    if (string.IsNullOrEmpty(s))
    {
        return "";
    }

    int start = 0;
    int end = 0;

    for (int i = 0; i < s.Length; i++)
    {
        int length1 = CenterNum(s, i, i);
        int length2 = CenterNum(s, i, i + 1);
        int length = Math.Max(length1, length2);
        if (length > end - start)
        {
            start = i - (length - 1) / 2;
            end = i + length / 2;                    
        }
    }

    return s.Substring(start, end - start + 1);
}

 

주어지는 문자열 s에 대하여 가장 긴 팰린드롬을 만드는 함수로

아래에 서술할 CenterNum 함수를 이용하여 짝수와 홀수의 경우 모두 확인하여 더 긴 팰린드롬을 찾는다.

이후 부분문자열로 해당 부분을 잘라내어 반환함으로 팰린드롬을 반환한다.

 

 

주어지는 문자열의 팰린드롬 찾기

public class Solution {
    public int solution(string s) {
        int answer = 0;

        answer = Plaindrome(s).Length;

        return answer;
    }
}

 

answer에 구현한 Palindrome 함수를 사용하여 가장 긴 팰린드롬의 길이를 구한다.

(기본적으로 팰린드롬의 string을 반환하게 구현하였으므로 .Length를 사용한다)

string을 반환하므로 찾은 팰린드롬도 확인할 수 있다.

 

 

오늘은 알고리즘 문제를 풀면서 팰린드롬(회문)이라는 문제를 풀었는데,

 

맨 처음에 알고리즘 문제책을 구매하였을 때, 접했던 1번 문제로 회문 찾기라는 문제가 기억나는 알고리즘 풀이였다.

 

그 당시에는 전혀 방법을 알지 못했지만, 지금은 여러 방법을 사용하여 문제를 풀 수 있었다.

 

특히 문제를 푸는 과정에서 중앙확장기법이라는 방법을 확인할 수 있었고 이를 응용해보는 시간을 가졌던 것이 좋았다.