15927 회문은 회문아니야!!

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

15927번: 회문은 회문아니야!!

 

애드혹은 항상 골 때린다

 

일단 처음 문제를 접했을 때는 투포인터인가? 싶었다

그런데 아무리봐도 left right 증감 조건을 찾기가 까다로웠다

그래서 일단 완탐으로 나이브하게 했더니 시간초과

그 후 좀 생각해보니 최대 길이 단 한번만 찾으면 되니,

그리디인가 싶어서 탑다운 완탐으로, 해를 하나라도 찾으면 break 하는 방식으로 바꿨더니

채점이 60%대 까지는 쑥쑥 올라갔다

그런데 67% 즈음에 저격테케 맞고 시간초과

그 후 곰곰히 생각해보니

worst case는 AAAAAA.... A 처럼 같은 문자열이 반복되는 경우밖에 없을 것 같아서

미리 O(N)의 시간을 좀 소모하고, 완전히 같은 문자열일 경우, 로직 진행 안하고 바로 -1을 출력하게 했더니

통과했다

 

https://github.com/KimximyaFan/Random-Defense/blob/main/C0029.java

 

위 링크는 내가 푼 방식의 코드이다

 

 

그 후 태그까니 애드혹이길래 뭘까 싶어서 찾아봤더니

발상만 있으면 쉽게 풀 수 있는 문제였다

 

1. 펠린드롬 체크는 전체 문자열 s에 대해서 한번만 하며,

2. 그 문자열이 펠린드롬이면, s.lengh() 출력

3. 문자열이 펠린드롬이 아니면, 뭘 어떻게 하든, 앞이든 뒤든 하나라도 빼면 대칭이 깨지므로, s.length() - 1 을 출력

4. 만약에 전체 문자열 s 가 한 문자로만 이루어져 있다면 이를 따로 검사해서 -1을 출력

 

로직은 위와 같으며

 

최적화는 다양하게 할 수 있는데

 

1. String을 쓰기보다는 Char[] 를 쓸 것

2. 한 문자로만 이루어져 있는지의 검사는 boolean을 이용해서, 순회시, 앞 문자열과 같은지 다른지를 이용해서 간단하게

 

https://github.com/KimximyaFan/Random-Defense/blob/main/C0030.java

 

위 링크는 270대ms 를 210대ms 까지 최적화한 코드이다