BOJ 35412 스택과 팰린드롬

먼저, 2번 단계에서 새로 만들어지는 팰린드롬은 반드시 마지막으로 추가된 글자를 포함합니다. 따라서 3번 단계가 발동될 일은 없습니다.

그리고 2번 단계에서 만들어진 팰린드롬이 길이 4 이상($= k$)이라면, 길이 $k$의 팰린드롬은 가운데에 길이 $k-2$의 팰린드롬을 포함하므로, 1번 단계 이전에 길이 $k-2$의 팰린드롬이 존재하게 되어 모순입니다.

따라서, 1번 단계에서 마지막 글자가 추가되었을 때 만들어질 수 있는 팰린드롬의 길이는 2 또는 3이며, 매 글자가 추가될 때마다 각각이 존재하는지 한 번씩만 확인하여 지워주면 됩니다. 길이 2와 길이 3을 테스트하는 순서는 상관 없습니다.