8934. 팰린드롬 공포증 D4

어제는 알바 끝나고 운동 갔다가 너무 피곤해서 못썼다... 하체 피로감 + 가슴, 어깨 하니까 집와서 바로 기절해 버렸다

그래서 오늘은 두 문제를 풀어보겠다ㄹ

일단 첫 번째 문제

앞 뒤로 뒤집어도 똑같은 문자열을 ‘팰린드롬’ 이라고 한다.

예를 들어, “o_o”, “404”, “appa” 는 팰린드롬 이지만, “umma”, “koosaga”, “kriii”는 팰린드롬이 아니다.

상욱이는 팰린드롬에 대한 공포증이 심해서, 어떠한 문자열에 길이 2 이상의 팰린드롬이 등장하는 것을 매우 싫어한다.

상욱이는 어느 날 ‘a’, ‘b’, ‘c’ 세 문자로만 이루어진 문자열을 받았다.

착한 재현이는, 문자열에 있는 문자들을 섞어서 길이 2 이상의 팰린드롬이 등장하지 않게 하려 한다. 

이것이 가능한지 판단하라.

[입력]

첫 번째 줄에 테스트 케이스의 수 TC가 주어진다.

이후 TC개의 테스트 케이스가 새 줄로 구분되어 주어진다.

각 테스트 케이스는 다음과 같이 구성되었다.

첫 줄에, ‘a’, ‘b’, ‘c’로만 이루어진 문자열 S가 주어진다. S의 길이는 1 이상 100000 이하이다.

 

[출력]
각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,
각 테스트 케이스마다 한 줄씩, S에 길이 2 이상의 팰린드롬이 등장하지 않게 할 수 있다면
YES, 아니면 NO를 출력한다.

대충 a,b,c로 이루어진 문장을 입력받아 이 문장을 조합했을 때 길이가 2이상인 펠린드롬이 나오면 안된다는 뜻이다. 그 말인 즉슨 aa,bb,cc와 같이 연속된 문자가 나오면 안된다는 뜻이다.

그래서 내 생각은 문장을 입력받고 문장의 a,b,c의 개수를 세서 가장 많은 것의 개수와 가장 적은 것의 개수를 뺐을 때 1보다 크면 aa와 같은 길이가 2인 펠린드롬을 만들 수 있다고 생각했다.

그래서 각 문자를 카운트 해 max와 min을 빼 1보다 크면 NO를 출력하면 된다.

#include <iostream>
#include <string>
 
using namespace std;
 
int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    int TC,acnt,bcnt,ccnt;
    string N;
    cin>>TC;
    for (int t=1;t<=TC;t++)
    {
        cin>>N;
        bool check = true;
        acnt=0,bcnt=0,ccnt=0;
        for(int i=0;i<N.length();i++)
        {
            switch (N[i]){
                case 'a':
                    acnt++;
                    break;
                case 'b':
                    bcnt++;
                    break;
                case 'c':
                    ccnt++;
                    break;
            }
        }
        int temp = max(max(acnt,bcnt),ccnt)-min(min(acnt,bcnt),ccnt);
        if(temp>1)
            check = false;
        if(check)
            cout<<'#'<<t<<" YES\n";
        else
            cout<<'#'<<t<<" NO\n";
    }
    return 0;
}
 

물론 이 방식은 문자가 3개 일때만 해당된다.

4개나 그 이상은 다른 알고리즘으로 풀어야 한다.