[프로그래머스 C#] Lv.3 가장 긴 팰린드롬

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

주어진 문자열의 모든 부분문자열 중에 가장 긴 팰린드롬 문자열을 찾는 문제

- 팰린드롬 문자열 : 뒤집어도 동일한 문자열이 되는 문자열

- 모든 부분문자열에 대해 판단해야 되기 때문에 모든 인덱스를 중심으로 완전탐색 해야 함

- 팰린드롬 문자열은 양 쪽 인덱스를 같은 개수로 제외시켜도 팰린드롬 문자열임

 

1) 팰린드롬 문자열을 찾는 방법

- 직접 문자열을 뒤집어서 Equals 메서드로 비교하면 비효율적이므로, 좌우로 이동할 포인터 위치를 받아 각 포인터 좌표의 문자가 같은지 비교하며 팰린드롬 문자열임을 판단하고 팰린드롬 문자열일 경우 각 좌우 포인터를 한칸씩 더 이동해 판단하는 것을 반복

-> 양쪽 포인터를 동시에 이동하며 판단해야 되기 때문에 길이가 홀수인 경우와 짝수인 경우를 따로 체크

 

주석 참조

    using System;

    public class Solution
    {
        public int solution(string s)
        {
            int answer = 1; // 최소 값

            for (int i = 1; i < s.Length; i++)
            {
                // 길이가 홀수인 팰린드롬 문자열 찾기
                Function(s, 1, i - 1, i + 1, ref answer);

                // 길이가 짝수인 팰린드롬 문자열 찾기
                Function(s, 0, i - 1, i, ref answer);
            }

            return answer;
        }
        
        public void Function(string s, int count, int leftIndex, int rightIndex, ref int answer)
        {
            // 범위 벗어남
            if (leftIndex < 0 || rightIndex >= s.Length)
                return;

            // 팰린드롬 문자열을 찾음
            if (s[leftIndex] == s[rightIndex])
            {
                count += 2;
                Function(s, count, --leftIndex, ++rightIndex, ref answer);
                answer = Math.Max(answer, count);
            }
        }
    }