백준 16161 가장 긴 증가하는 팰린드롬 부분수열

이름이 참 길다. 그리고 그 이름이 내용을 전부 말해준다.

팰린드롬 수열은, 앞에서부터 읽을때와 뒤에서부터 읽을 때 모두 같은 수열을 말한다. 한때 유행어였던, 내이름은 이효리 거꾸로해도 이효리 의 숫자 버전이라고 할 수 있다.

근데 또 이 수열이 증가해야한다. 팰린드롬 수열의 중간(반복되기 시작하는 지점)까지 계속 수가 늘어나야 한다. 같아도 안된다.

주어진 수열에서 해당 조건에 맞는 가장 긴 수열의 길이를 구하는 문제이다.

 

처음, 모든 수열의 체크할 수는 없고, 무조건 연속되어야 하니 투 포인터를 사용해 접근했다.

투 포인터에 대한 자세한 설명은 여기 되어있다. L과 R을 하나씩 움직이며 수열을 체크했다.

 

우리의 L과 R은 처음에 모두 0으로 설정되어있다. 이때, 현재 R과 그 다음이 연속적으로 계속 커지면 R을 늘린다.

그렇게 R을 늘리다가, 펠린드롬 수열인지 체크하는 시점은 이제 더이상 연속적으로 늘지 않을때다.

이 때 R과 R다음 수가 같으면, 짝수개의 수열을 체크하고 다르면 홀수개의 수열을 체크하는 분기가 된다.

 

펠린드롬 수열인지 체크하는건 간단하다. - 생각하는데 오래 걸리긴 했는데 코드가 짧으니 간단한걸로 하자...- 우리가 생각하고 있는 중심부부터 하나씩 늘리며 양쪽을 비교하면 된다. 그렇게 같을 때까지 길이를 재고 우리가 답으로 출력할 변수를 업데이트 해준다.

 

그 뒤, L을 R 다음값으로 옮겨준다. R 이전의 팰린드롬 수열을 체크한것이므로, 그 이후로 가는것은 의미가 없다...

---

#include <iostream>

int main()
{
    int N;
    std::cin >> N;
    int list[N];
    for (int i = 0; i < N; i++)
    {
        std::cin >> list[i];
    }

    int lpointer = 0;
    int rpointer = 0;
    int maxLen = 1; //0이면 안됨.

    while(lpointer <= rpointer && rpointer < N - 1)
    {
        if (list[rpointer] < list[rpointer + 1])
            rpointer++;
        else if (list[rpointer] == list[rpointer + 1])
        {
            int i = 0;
            for (i = 0; i <= rpointer - lpointer; i++)
            {
                if (rpointer + 1 + i >= N || list[rpointer - i] != list[rpointer + 1 + i])
                    break;
            }
            maxLen = std::max(maxLen, 2 * i );
            lpointer = rpointer + 1;
            rpointer++;
        }
        else
        {
            int i = 0;
            for (i = 0; i < rpointer - lpointer; i++)
            {
                if (rpointer+1 +i >= N || list[rpointer-1-i] != list[rpointer + 1 + i])
                    break;
            }
            maxLen = std::max(maxLen, 2 * i + 1 );
            lpointer = rpointer + 1;
            rpointer++;
        }
    }
    std::cout << maxLen;
}

처음에는 L과 R을 하나씩 늘리며 팰린드롬 수열인지 체크했는데, 시간 초과가 떴다. 그래서 이렇게 저렇게 삽질하다가 찾아보니 매번 조건을 찾을 필요 없이, R로 탐색이 불가능할때 한번에 검색해버리면 많이 시간을 아낄 수 있어서 그 방향으로 수정했다.

풀다가 중간에 막혀서 한없이 낙하하다가 몇번 던지고 다시 잡아서 풀었다. 진짜 급한 마음은 어떻게 한번에 딱 뭉쳐서 쓰레기통으로 버려버리고 싶다... 차분히 풀기...

 

오늘도 평온한 하루가 되길. 슨민.