[백준 - Python] 21925 - 짝수 팰린드롬

0.  문제 링크

 

 

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

21925번: 짝수 팰린드롬

---

1.  풀이 방법

 

 

1. 스택이 비어있다면, 매 숫자마다 스택에 넣는다. 그리고 다음 숫자로 이동한다.
2. 만약에 스택에 숫자가 들어가 있다면, 스택의 길이를 측정한다 -> l
   1. 현재 숫자의 위치인 cur과 스택의 마지막 숫자를 비교하며 좌우로 넓혀가며 팰린드롬을 만족하는지 확인한다.
      1. 이때 스택의 길이가 남은 숫자의 길이보다 길다면 이 또한 팰린드롬을 만들 수 없다.
   2. 만약 스택에 들어있는 숫자 3개와 현재 숫자의 위치인 cur에서 cur + 2까지의 3개의 숫자가 팰린드롬을 만족한다면, 스택을 모두 비운다. 그리고 True와 cur + l을 반환한다.
   3. 만약 아니라면 False를 반환한다.
3. 최종적으로 스택에 숫자가 남아있다면 -1을 반환, 남아있지 않다면 정답을 출력하면 된다.

---

2.  코드

 

 

import sys
input = sys.stdin.readline


def check(cur):
    l = len(stack)
    for i in range(l):

        if cur + i >= n:
            print(-1)
            exit(0)

        if stack[-i - 1] != maps[cur + i]:
            return False, 0

    stack.clear()
    return True, cur + l


if __name__ == "__main__":
    n = int(input())
    maps = list(map(int, input().split()))

    stack = []
    ans = 0
    i = 0

    while i < n:
        if len(stack) == 0:
            stack.append(maps[i])
            i += 1
        else:
            flag, next = check(i)
            if flag:
                ans += 1
                i = next
            else:
                stack.append(maps[i])
                i += 1

    if len(stack) > 0:
        print(-1)
    else:
        print(ans)

---

3.  마무리