[Python 3] BOJ - 16161 "가장 긴 증가하는 팰린드롬 부분수열"

 # 문제 링크

https://www.acmicpc.net/problem/16161

16161번: 가장 긴 증가하는 팰린드롬 부분수열

 

 # 풀이

 개인적으로 이 문제의 핵심은 투 포인터라고 생각한다.

<그림 1. [1,3,5,3,1]의 경우>

 위 그림 1은 문제에서 정의하는 증가하는 팰린드롬 수열의 예시인 [1,3,5,3,1]을 나타낸 그림이다. 그런데 위에서부터 2번째 그림인 [3,5,3]은 첫번째 수열의 부분수열임을 알 수 있고 [3,5,3] 역시 문제에서 정의하는 증가하는 팰린드롬 수열을 만족한다. 그런데 위에서부터 3번째 그림인 [5,3,1] 수열은 [3,5,3]과 마찬가지로 [1,3,5,3,1]의 부분수열임에도 불구하고 문제에서 제시하는 증가하는 팰린드롬의 수열의 정의를 만족하지 않는다. 두 수열의 차이는 수열의 중앙부분(3)이 원래 수열의 중앙부분(5)과 같지 않다는 것이다. 그런데, 위에서부터 4번째 그림은 세번째 수열처럼 수열의 중앙부분(3)이 원래 수열의 중앙부분(5)과 다름에도 불구하고 길이가 1이기 때문에 문제에서 정의하는 증가하는 팰린드롬 수열을 만족한다. 

 그런데 이미 [1,3,5,3,1]이라는 길이 5인 증가하는 팰린드롬 수열을 이미 만들었기 때문에 그림 1에서 제시하는 [3,5,3] 혹은 [3]과 같이 더 짧은 길이의 증가하는 팰린드롬 수열은 굳이 탐색할 필요가 없다. 

<그림 2. 예제 입력 1의 경우>

 위 그림 2는 예제 입력 1의 경우 중 일부를 나타낸 그림이다. 이 때 초록색 글씨는 수열의 중심, 빨간색 글씨는 그 다음 두 경계, 파란색 글씨는 증가하는 팰린드롬 수열의 구성 원소라고 하자. 첫번째 그림에서는 3을 기준으로 양쪽의 1을 검사하는 과정이다. 이 때 중심인 3보다 양쪽의 수가 작으므로 양쪽으로 확장할 수 있다.

 그런데 두번째 그림에서는 양쪽을 탐색하려고 했을 때 범위를 벗어나는 경우가 있기 때문에 더이상 탐색을 진행할 수 없다. 따라서, 3을 기준으로 하는 증가하는 팰린드롬 수열의 길이는 3개이다.

<그림 3. 예제 입력 1의 경우>

 위 그림 3은 그림 2의 후속 과정을 나타낸 그림이다. 그림 1의 논리로 인해 중심점이 1이 아닌 5가 된다. 이후 양쪽을 비교했을 때 양쪽의 수가 다르기 때문에 현재 5에서는 길이 1이 최대가 됨을 알 수 있다

<그림 4. 예제 입력 1의 경우>

 위 그림 4의 경우 역시 그림 3의 후속 과정을 나타낸 그림이다. 그런데 이번에는 그림 3과 차이가 있다. 가장 상단의 그림을 보면 그림 3의 논리처럼 접근하는데, 이렇게 된다면 현재 7에서는 길이 1이 최대가 됨을 알 수 있다. 왜냐하면 양끝의 수가 5와 7로서 서로 다르기 때문이다. 그런데 두번쨰 그림처럼 접근하게 되면 결과적으로 길이가 4가 된다. 왜냐하면 중심이 하나가 아니라 2개이기 때문이다. 따라서, 빨간색 글자, 즉 양쪽을 확장시켜 나가기 전에 중심에 위치한 수로 부터 오른쪽으로 봤을 때 같다면 중심을 늘리는 것이 이득이다. 

 이 때 주의해야 할 점이 있는데, 만일 [3,7,7,7,3]의 경우에는 정답이 5가 아니라 2([7,7])라는 점이다. 왜냐하면 중심으로 갈 수록 값이 증가해야 하기 때문이다. 세 개의 7중 두번째의 7이 중심이 되는데, 첫번째 7은 중심과 같기 때문에 증가하지 않기 때문이다. 또한 [1,1,1,1]의 경우도 마찬가지로 정답이 4가 아니라 2([1,1])이다. 왜냐하면 중심이 두번째 1과 세번째 1의 사이 어딘가라고 했을 때, 첫번째 1은 두번째 1과 같기 때문에 중심으로 들어올 수록 증가하지 않기 때문이다. 

 

 # 코드

import sys

# 입력부
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

# start : 중심 시작 위치
start = 0
ans = 0
while start < n:
    # end : 중심 끝 위치
    end = start
    # 중심의 길이를 늘릴 수 있는지 확인 (최대 길이 2)
    while end + 1 < n and arr[end + 1] == arr[start] and end + 1 - start < 2:
        end += 1
    # 양 쪽으로 확장
    i, j = start - 1, end + 1
    # size : 현재 중심이 [start, end]일 때 증가하는 팰린드롬 수열의 길이
    size = end - start + 1
    # val : 현재 수열의 가장 바깥쪽 값
    val = arr[start]
    
    # i,j가 범위를 만족하고 두 수가 같으며, val보다 작은 경우만 확장
    while i > -1 and j < n:
        if arr[i] == arr[j] and arr[i] < val:
            val = arr[i]
            i -= 1
            j += 1
            size += 2
        else:
            break
            
    # 정답 갱신 및 중심 시작을 가장 오른쪽으로 변경
    ans = max(ans, size)
    start = j
    
# 정답 출력
print(ans)