Codeforces Round #750 (Div. 2)-C. Grandma Capa Knits a Scarf

문제 설명

카파 할머니는 스카프를 짜기로 하셨고 수아 할머니에게 패턴을 짜달라고 부탁하셨다. 패턴은 영어 소문자로 이루어진 문자열인데, 수아 할머니는 길이가 $n$인 문자열 $s$를 적었다.

카파 할머니는 스카프를 아름답게 만들고 싶은데 할머니의 생각으로는 문자열 패턴이 팰린드롬으로 이루어져야만 스카프가 아름답다고 말한다. 카파 할머니는 수아 할머니가 쓴 패턴을 바꾸고 싶은데, 수아 할머니를 기분나쁘게 하지 않기 위해서 영어 소문자 하나를 정하고 그 문자만 문자열에서 제거하기로 했다. 이때 문자를 제거하는 수는 몇개든지 상관 없다. 한번도 제거 안할 수 있고 다 제거할 수도 있다.

카파 할머니는 패턴에서 제거해야할 문자의 수를 최소화 하고 싶다. 할머니를 위해 문자열 $s$가 팰린드롬이 되기 위해서 제거해야할 문자의 최소 개수를 구하자.

오른쪽으로 읽어도, 왼쪽으로 읽어도 같은 문자열이 될 때 그 문자열은 팰린드롬이라고 한다. 예를 들어 문자열 "kek"와 "abacaba", "r", "papicipap$는 팰린드롬이지만 문자열 "abb"와 "iq"는 팰린드롬이 아니다.

Input
첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t(1\le t\le 100)$ 이 주어진다.

각 테스트케이스의 첫번째 줄에는 문자열의 길이 $n(1\le n\le {10}^5)$ 가 주어진다.

각 테스트케이스의 두번째 줄에는 영어 소문자로 이루어진 길이가 $n$인 문자열 $s$가 주어진다.

Output
각 테스트케이스마다 문자열을 팰린드롬으로 만들기 위해서 지워야할 문자의 최소 개수를 구하자 만약 불가능 하다면 $-1$을 출력한다.

Example
input
5
8
abcaacab
6
xyzxyz
4
abba
8
rprarlap
10
khyyhhyhky

output
2
-1
0
3
2

문제 접근

사용한 알고리즘: 그리디 알고리즘, 완전탐색, 구현, 투포인터
걸린 시간 : 00:06
아니 이거 왜 못품? 진짜 답만 보면 내가 무조건 시간안에 풀 수 있을 거 같은데 대회때만 되면 어떻게 푸는지 뇌정지 와서 결국 못풀었다. 이 문제 이제 거뜬하게 풀 수 있어야 뉴비 탈출하고 본격적으로 파랑단 도전할 수 있는데 벌써 부터 화딱지 난다. 계속 화딱지 나야 내 실력이 늘 수 있을까? 이럴때마다 알고리즘 공부하기 진짜 싫어지는 순간이다. 이걸 얼마나 참아야 하는지 잘 모르겠다.

단순한 구현문제, 투 포인터 문제이다. 결국 모든 알파벳을 고려해서 풀면 되는데 팰린드롬 문제는 푸는 방법이 어느정도 정형화 되어있다. 결국 맨 앞과 맨 뒤에서 차례대로 문자를 비교하면서 문자가 같으면 안쪽으로 이동, 문자가 다르면 팰린드롬이 아니라고 하는 것이 정석이다. 그런데 이 문제는 한 종류의 문자를 지울 수 있다! 따라서 지울 수 있는 문자가 있다면 그 문자를 지웠다고 카운팅 해주고 인덱스를 옮긴다. 그 다음에 다시 문자를 비교하는 방법을 반복하면 된다.

이 쉬운걸 왜 대회때는 못 풀었을까? 코드포스 하면서 민트까지는 금방 갈거 같은데..., 이번 년도에는 꼭 민트라도 가고 싶다.

정답 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        string s; cin >> s;
        int ans = n + 1;
        for(char c = 'a'; c <= 'z'; c++){
            int l = 0, r = n - 1, cnt = 0;
            while(l <= r){
                if(s[l] == s[r]) l++, r--;
                else if(s[l] == c) l++, cnt++;
                else if(s[r] == c) r--, cnt++;
                else{
                    cnt = n + 1;
                    break;
                }
            }
            ans = min(ans, cnt);
        }
        cout << (ans == n + 1 ? -1 : ans) << "\n";
    }
    return 0;
}