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

문제 설명

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

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

 

제한 사항

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

 

프로그래머스

 

 

1차 시도 - 실패한 풀이 코드

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int solution(string s) {
        
        List<int> list = new List<int>();

        string temp = "";

        for (int i = 0; i < s.Length; i++)
        {
            for (int j = i; j < s.Length; j++)
            {
                temp += s[j];
                string r = "";
                if (1 < temp.Length)
                {
                    r = new string(temp.Reverse().ToArray());
                }

                if (s.Contains(r))
                {
                    if (!list.Contains(temp.Length))
                    {
                        list.Add(temp.Length);
                    }
                }
            }

            temp = "";
        }

        return list.Max();
    }
}

생각나는 대로 작성해 본 코드! 처참하게 실패

 

2차 시도 - 실패한 풀이 코드 (슬라이딩 윈도우 사용)

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int solution(String s)
    {
        if (s.Length <= 1) return 1;

        List<int> list = new List<int>();

        for (int window = 1; window < s.Length + 1; window++)
        {
            for (int j = 0; j <= s.Length - window; j++)
            {
                if (isPandrome(s.Substring(j, window)))
                {
                    list.Add(window);
                    break;
                }
            }
        }

        return list.Max();
    }

    public bool isPandrome(string s)
    {
        if (s.Length <= 1) return true;

        if (s[0] == s[s.Length - 1])
        {
            return isPandrome(s.Substring(1, s.Length - 2));
        }

        return false;
    }
}

 

효율성 검사에서 자꾸 실패해서 찾아보니 Substring 함수를 쓰면 안 된다고 해서 쓰지 않는 코드로 변경

 

 

풀이 코드 (슬라이딩 윈도우 + Substring 함수 사용하지 않기)

using System;
using System.Linq;

public class Solution {
    public int solution(String s)
    {
        if (s.Length <= 1) return 1;

        int count = 0;

        for (int window = s.Length; 0 < window; window--)
        {
            if (window < count) return count;

            for (int j = 0; j + window <= s.Length; j++)
            {
                if (isPandrome(s, j, j + window))
                {
                    if (count < window)
                    {
                        count = window;
                    }

                    return count;
                }
            }
        }

        return count;
    }

    public bool isPandrome(string s, int start, int end)
    {
        if (s.Length <= 1) return true;
        if (end < start) return true;

        if (s[start] == s[end - 1])
        {
            return isPandrome(s, start + 1, end - 1);
        }

        return false;
    }
}

 

함께 읽으면 좋은 글

C# Substring 복습하기