C# 가장 긴 팰린드롬 - 투 포인터 / 프로그래머스 [Lv.3]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/12904

 

 

나의 풀이

public int solution(string s) 
{
    int answer = 1;

    for(int i = 1; i < s.Length - 1; ++i)
    {
        // 홀수 구성 체크 aba
        Check(s, 1, i, i, ref answer);

        // 짝수 구성 체크 abba
        if(s[i] == s[i + 1])
            Check(s, 2, i, i + 1, ref answer);
    }

    return answer;
}

void Check(string s, int startCount, int left, int right, ref int answer)
{            
    int count = startCount;

    while(true)
    {
        if(--left < 0) break;
        if(++right >= s.Length) break;
        if(s[left] != s[right]) break;
        count += 2;
    }

    if(count > answer)
        answer = count;
}

부분수열을 구하는게 아니라 부분수열의 길이를 구하는 문제.

완전탐색으로 하나씩 시작점을 잡은 다음 좌우로 포인터를 움직이며 체크해주면 된다.