[BOJ][C#] 17609 회문

📕 문제

📌 링크

📗 접근 방식

주어진 조건에 따라 회문이면 0, 한 문자를 삭제하면 회문이 되면 1, 그 외의 경우는 2를 반환하는 함수 IsPalindrome을 작성합니다.

IsPalindrome 함수는 주어진 문자열과 양 끝 인덱스를 받아 양끝에서 가운데로 이동하면서 문자가 서로 다른 경우를 체크합니다. 만약 서로 다른 문자가 나오면, 한 문자를 삭제할 수 있는 경우인지 판단하기 위해 IsSimilarPalindrome 함수를 호출하고, 그 결과를 반환합니다.

IsSimilarPalindrome 함수는 현재 문자열에서 한 문자를 삭제하면 회문이 되는지 판단합니다. 양 끝에서 한 칸씩 좁혀가면서 비교하며 다른 문자가 나오면, 왼쪽 문자를 삭제하거나 오른쪽 문자를 삭제한 결과 중에서 회문이 되는 경우를 찾아 반환합니다.

📘 코드

정답 코드

using System.Text;

namespace BOJ_17609
{
    class Program
    {
        static void Main()
        {
            StringBuilder sb = new StringBuilder();

            string s;
            int n = int.Parse(Console.ReadLine());

            while (n-- > 0)
            {
                s = Console.ReadLine();
                sb.AppendLine(IsPalindrome(s, 0).ToString());
            }

            Console.Write(sb);
        }

        static int IsPalindrome(string s, int count)
        {
            int left = 0;
            int right = s.Length - 1;

            while (left < right)
            {
                if (s[left] != s[right])
                {
                    return count != 0 ? 2 : IsSimilarPalindrome(s, left, right - left);
                }
                
                left++;
                right--;
            }

            return 0;
        }

        static int IsSimilarPalindrome(string s, int left, int length)
        {
            if (IsPalindrome(s.Substring(left + 1, length), 1) == 0 ||
                IsPalindrome(s.Substring(left, length), 1) == 0)
            {
                return 1;
            }

            return 2;
        }
    }
}

메모리 초과 코드

using System.Text;

namespace BOJ_17609
{
    class Program
    {
        static void Main()
        {
            StringBuilder sb = new StringBuilder();

            string s, s1, s2;
            int n = int.Parse(Console.ReadLine());
            int left, right, count;

            while (n-- > 0)
            {
                s = Console.ReadLine();

                if (IsPalindrome(s))
                {
                    sb.AppendLine("0");
                }
                else if (IsSimilarPalindrome(s))
                {
                    sb.AppendLine("1");
                }
                else
                {
                    sb.AppendLine("2");
                }
            }

            Console.Write(sb);
        }

        static bool IsPalindrome(string s)
        {
            // 짝수일 때
            if (s.Length % 2 == 0)
            {
                int mid2 = s.Length / 2;
                int mid1 = mid2 - 1;

                while (mid1 >= 0 || mid2 < s.Length)
                {
                    if (s[mid2] != s[mid1])
                    {
                        return false;
                    }

                    mid2++;
                    mid1--;
                }
            }
            // 홀수일 때
            else
            {
                int mid1 = s.Length / 2;
                int mid2 = mid1;

                while (mid1 >= 0 || mid2 < s.Length)
                {
                    mid2++;
                    mid1--;
                    
                    if (s[mid2] != s[mid1])
                    {
                        return false;
                    }
                }
            }

            return true;
        }

        static bool IsSimilarPalindrome(string s)
        {
            for (int i = 0; i < s.Length; i++)
            {
                string temp;
                
                if (i == 0)
                {
                    temp = s.Substring(1, s.Length - 1);
                }
                else if (i == s.Length - 1)
                {
                    temp = s.Substring(0, s.Length - 1);
                }
                else
                {
                    temp = string.Concat(s.Substring(0, i), s.Substring(i + 1, s.Length - i - 1));
                }

                if (IsPalindrome(temp))
                {
                    return true;
                }
            }
            
            return false;
        }
    }
}

📙 오답노트

처음에 생각나는 대로 코드를 작성하여 풀어봤는데 string을 남발하여서 메모리 초과가 난 것 같다. 그 이후 중심에서 뻗어 나가는게 아니라 양측 끝에서 시작하여 중심으로 오는 로직으로 수정하였고 좌우값이 다를 때 그 앞에(왼쪽이면 left+1, 오른쪽이면 right-1) 있는 값과 비교하는 로직을 사용하였지만 abcddadca이 반례를 찾고 일정 부분 참고하여 코드를 작성하였다.

string은 너무 어렵다..

📒 알고리즘 분류

• 문자열
• 투 포인터