[백준] 짝수 팰린드롬

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

21925번: 짝수 팰린드롬

반례 찾기가 힘들었던 문제입니다. 스택으로 탐색하면서 짝수 팰린드롬을 만족하는 경우 매칭되는 문자의 인덱스를 저장해둡니다. 단순히 스택만 이용했을 때에는 짝수 팰린 드롬을 만족하지 못하는데에도 정답이라고 나오는 경우가 있습니다. 매칭되는 문자의 인덱스를 저장한 다음 이것을 짝수 팰린드롬을 만족하는지 체크하는데에 사용됩니다.

 

import sys

# sys.stdin = open("input.txt", "r")

# 숫자의 개수
n = int(input())
# 숫자들
nums = list(map(int, input().split()))

stack = []
answer = 0
pelin_idx = [-1] * n
visited = [False] * n

for i in range(n):
    # 스택이 비어있거나 스택의 top과 현재 숫자가 다른 경우에는 스택에 넣는다.
    if not stack or nums[stack[-1]] != nums[i]:
        stack.append(i)
        continue

    # 짝수 팰린드롬을 만들 수 있는 경우
    # 펠린드롬으로 매칭되는 인덱스를 저장한다.
    if stack and nums[stack[-1]] == nums[i]:
        pelin_idx[stack[-1]] = i
        pelin_idx[i] = stack[-1]
        stack.pop()

def check_pelin(left, right):
    if left == -1 or right == -1:
        return False

    while left < right:
        left_num = nums[left]
        right_num = nums[right]

        if left_num != right_num:
            return False
        visited[left], visited[right] = True, True

        left += 1
        right -= 1
    return True

for i in range(n):
    if visited[i]:
        continue

    left = i
    right = pelin_idx[left]

    if not check_pelin(left, right):
        print(-1)
        sys.exit(0)
    else:
        answer += 1

print(answer)