A. 문제설명
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW5jJcZ68LsDFATQ
문제에 대한 자세한 설명은 링크 참조
1. 앞뒤로 뒤집어도 똑같은 문자열을 팰린드롬이라고 한다.
2. 예를 들어, “o_o”, “404”, “appa” 는 팰린드롬 이지만, “umma”, “koosaga”, “kriii”는 팰린드롬이 아니다.
3. a,b,c로 이루어진 주어진 문자열 내 길이가 2이상인 팰린드롬을 없애고자 한다.
4. 여기서 주어진 문자열내 문자들은 각각 바꿀 수 있으며 해당 주어진 문자열의 서브스트링이 팰린드롬이어도 팰린드롬이다.
5. 문제에서 각 문자열이 주어질 때, 해당 문자열을 수정하여 팰린드롬이 아닌 것으로 바꿀 수 있으면 YES, 아무리 바꾸어도 팰린드롬인 것이면 NO 출력
B. 접근법
먼저 일반적인 방법으로 문자열과 그 내부 문자열의 팰린드롬 여부를 확인하는 것은 메모리 초과가 되어버린다.(최대 길이 100000인 문자열의 서브스트링을 모두 검사하면 그 비용이 지수적으로 되어버림)
그렇다면, 문제에서 주어진 조건과 팰린드롬의 성질을 파악하여 접근하여야 한다는 것이다.
먼저, a,b,c의 문자만이 주어지는 해당 문제에서 만들 수 있는 팰린드롬이란 어떤 것인가?
aa(o), bb(o), aba(0), bba(o), aabb(o), aabc(o), ...
그러면 만들 수 있는 팰린드롬이 아닌 문자열은 어떤 것인가?
abcabcabc(x), acbacbacb(x), ...
세 개의 문자가 겹치지 않으면서 계속 반복되어 나타나야 한다.
여기서, 사실상 문자열이 길어져도 반복되는 패턴상 길이 3이내의 서브스트링만 파악하면 그 문자열이 팰린드롬인지 아닌 지 파악할 수 있다.
즉, 팰린드롬이 아니려면 a,b,c이 등장횟수가 모두 같거나 마지막 문자 패턴 하나만 남기고 해당 패턴이 반복되어야 하는데, 가장 많이 등장하는 문자인 max와 가장 적게 등장하는 문자인 min의 차를 비교하여 max-min이 1보다 큰 경우, 어떻게 바꾸어도 팰린드롬이 된다.
|a(max)| = 4, |b| = 3, |c(min)| = 2
abcabcaab(o), abcabcaba(o), abcabcbaa(o)
이렇게 말이다...
C. 풀이
1. 각 주어진 문자열내 a,b,c의 등장횟수를 계수
2. 가장 많이 등장하는 문자인 max와 가장 적게 등장하는 문자인 min의 차를 비교
3. max-min이 1보다 큰 경우, 어떻게 바꾸어도 팰린드롬, 그 반대는 팰린드롬이 아닐 수 있다.
D. 내 코드
