[백준 16161번] 가장 긴 증가하는 팰린드롬 부분수열 (Python3)

N,data = int(input()),[*map(int,input().split())]

result = 1
i = 0
while i < N-1:
  if data[i] > data[i+1]:
    i += 1
    continue
  if data[i] == data[i+1]:
    result = max(result,2)
    i += 1
    continue
  stack,l = [data[i]],1
  while i<N-1 and data[i]<data[i+1]:
    stack.append(data[i+1])
    i += 1
  if i<N-1 and data[i+1]==stack.pop():
    l += 1
    i += 1
  while stack and i<N-1 and data[i+1]==stack.pop():
    l += 2
    i += 1
  result = max(result,l)
print(result)

투 포인터 알고리즘으로 해결하였다.

핵심 포인트는 팰린드롬 부분수열이 증가하다가 감소해야하기 때문에, 감소하는 지점까지 탐색을 하고 나면 이전의 구간은 탐색할 필요가 없다는 것이다. 어차피 마지막 지점이 감소로 끝났기 때문에, 그 이후부터 탐색을 시작해야한다.

 

이를 토대로 설명하면,

1. i=0부터 탐색을 시작한다. 다음 값이 현재 값보다 작으면 continue, 같으면 2로 result로 갱신 후 continue 한다.

2. 다음 값이 현재 값보다 큰 경우, 증가가 유지될 때까지 stack에 숫자를 쌓아준다.

3. 증가가 멈추면, 만약 다음 값이 마지막 값과 같은 경우 팰린드롬 길이를 +1을 해주고 감소구간 탐색을 시작한다.

4. stack의 숫자들을 하나씩 pop 해주면서 다음 값과 비교한다. 같은 경우 팰린드롬 길이를 +2 해준다.

5. 같지 않은 경우 새로운 팰린드롬 탐색을 시작한다.

6. 가장 긴 길이를 출력한다.

 

 

오늘의 교훈) 다양한 팰린드롬 문제를 풀어보자