C언어 4제] 2019년 한국정보올림피아드 1차대회 초등부 2번 - 회문

문제] [유형3] 2번 - 회문 (100점)

모든 언어에 대해 시간 제한 2초, 메모리 제한 512MB입니다.

회문 또는 팰린드룸(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 'abba','kayak', 'reviver', 'madam'은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 "유사회문"(pseudo palindrome)이라고 부른다, 예를 들어 'summuus'는 5번째나 혹은 6번째 문자 'u'를 제거하여 'summus'인 회문이 되므로 유사회문이다.

여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 석제하면 회문이 되는 "유사회문"인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그외는 2를 출력해야한다.


입력형식]
입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1≤ T ≤30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3이상 100000이하이고, 영문 알파벳 소문자로만 이루어져 있다.


출력형식]
각 문자열이 회문인지, 유사회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 휴사회문이면 1, 둘 모두 아니면 2를 순서대로 한줄에 하나씩 출력한다.


입력 1]
7
abba
summuus
xabba
xabbay
comcom
comwwmoc
comwwtmoc

출력 1]
0
1
1
2
2
0
1

 

참고풀이]

#include <stdio.h>
#include <stdlib.h> //malloc(), free()
#include <string.h> //strlen(), strcpy()

int main()
{
   int T;//문자열의 개수를 입력받는다.
   char str[255];//임의의 문자열을 입력할 문자열 배열변수 
   int r,c;//행,열변수
   int c1,c2;//열변수 
   int chk1,chk2,chk3;//회문, 유사회문, 비회문 변수 
   int i;//반복변수 
   int N;//체크할 문자열의 길이 

   //개수를 입력받는다.
   scanf("%d%*c",&T) ;

   //1<=T<=30 조건에 맞으면 작업을 계속한다.
   if(T>=1 && T<=30) 
   {
      //입력된 개수만큼의 문자열을 입력할 동적메모리를 설정한다.
      char **M=(char **)malloc(sizeof(char *)*T);
      for(r=0;r<T;r++)
      {
         //문자열을 입력한다.
         scanf("%s%*c",str);
         if(strlen(str)>=3 && strlen(str)<=100000)
         {
            M[r]=(char *)malloc(sizeof(char)*(strlen(str)+1));
            strcpy(M[r],str);
         }
         else
            return 0;
      }

      //입력된 문자열이 회문, 유사회문, 둘다 아닌지 체크한다.
      for(r=0;r<T;r++) 
      {
         //문자열 중 틀린 글자가 나오면 회문이 아님 
         //틀린 문자의 위치를 회문체크변수에 저장.
         //회문이면 출력한다.
         chk1=-1;//회문체크변수
         N=strlen(M[r]);
         for(c=0;c<N/2;c++)
            if(M[r][c] != M[r][N-1-c])
            {
               chk1=c;
               break;
            }
         if(chk1==-1){
            printf("0\n");
         }
         else
         {
            //유사회문 또는 비회문인지 체크한다.
            c1=c2=0;
            chk2=0;chk3=0;
            char *chkStr1=(char *)malloc(sizeof(char)*(strlen(M[r])+1));
            char *chkStr2=(char *)malloc(sizeof(char)*(strlen(M[r])+1));//비교할 문자열 변수 
            //틀린 위치의 문자를 뺀 문자들을 각각의 변수에 저장한다.
            for(i=0;i<N;i++) 
            {  
               if(i != chk1) chkStr1[c1++]=M[r][i];
               if(i != N-1-chk1) chkStr2[c2++]=M[r][i];
            }

            //각각의 문자들을 비교하여 유사회문, 비회문을 체크한다.
            for(i=0;i<N-1;i++)
            {
               if(chkStr1[i] != chkStr1[N-2-i]) chk2=1;
               if(chkStr2[i] != chkStr2[N-2-i]) chk3=1;
            }
            if(chk2==1 && chk3==1)
               printf("2\n");
            else
               printf("1\n");

            free(chkStr1);
            free(chkStr2);
         }
      }

      for(r=0;r<T;r++)
         free(M[r]);
      free(M);
   }
 
   return 0;
}

 

참고풀이 결과]

 

 

 

대한민국의 아름다운 영토, 독도의 가을