Special Palindrome

문제를 잘 파악하자!

생각한 것

왜 저렇게 크게 써놨냐면 문제를 제대로 파악을 못해서 잘못된 코드를 짰기 때문이다. 결국 처음에는 그냥 일반적인 팰린드롬을 구현했다(효율적인지는 둘째치고...). 그러다 테스트 케이스가 실패하는걸 보고 문제를 다시 보니 "한 문자 빼고 전부 다 같은 경우"가 있었고 일반적인 팰린드롬은 다른 것들도 카운팅 해주기 때문에 실패한다는 걸 알았다.

또 삽질

그런데 나는 정말 생각없이 "단 하나"임을 놓치고 가운데에 오는 문자가 하나인 것과(홀수 길이) 두개인 것(짝수 길이)을 따로 체크를 해주도록 코드를 작성했다... 그러니 틀릴 수 밖에. 게다가 쓸데없는 연산이 생겼기 때문에 타임아웃에 걸리는건 덤...

 

이런 괴악한 코드가...

진짜 해결책

우선 먼저번에 구현한 "잘못된 팰린드롬"과 같은 방식으로 구현하면 타임아웃에 걸릴 것 같았다. 그래서 수학적 연산으로 총 연산 수를 줄이고자 했고, "모두 같은 문자로 이루어진 경우"에서 그 포인트를 찾았다. 모두 같은 문자로 이루어진 문자열에서 나올 수 있는 부분 집합의 개수는 n*(n+1)/2 (n은 문자열 길이)이기 때문에 n시간 안에 연산을 마칠 수 있다. 그리고 하나만 다른 팰린드롬은 한번 더 순회하면서 판단해주면 된다.

결말

문제를 잘 파악하자. 시작부터 꼬이면 모든 노력이 물거품이 된다.