[D3] SWEA 19003. 팰린드롬 문제

(*무시해도 됨*)

'''

처음에는 N 개의 문자열 중

1,2,3, ~ , N개를 고르고 조합해본 뒤,

(ex=nC3)

회문인 지 아닐까 판단하려고 했다.

하지만 n의 최대값이 100으로 크므로

소규모 교전(나만의 표현 방식)이 아니라 제외했다.

이런 촌스러운 방식을 사용하는 문제는 나오지 않는 것으로 보인다.

'''

1. 접근 방식

결국, 조합된 문자열이 회문인가 아닌가를 판단하는 문제다.

 

이럴 땐, 갯수가 1부터 시작해서 살펴보면 된다.

 

1)문자열의 갯수가 1일 때

ex) aba, aaa, cbc 

스스로 회문이면 된다.

 

2)문자열의 갯수가 2일 때

abccba => abc,cba 서로가 역순

adddddda => addd ddda 서로가 역순

 

3)문자열의 갯수가 3일 때

abcfffcba ->abc+fff+cba =>역순+스스로 회문+역순

dfsbfbsfd -> dfs+bfb+sfd =>역순+스스로 회문+역순

 

4)문자열의 갯수가 4일 때

abcdfssfdcba-> abc+dfs+sfd+cba =>역순1 + 역순2 + 역순2 + 역순1

 

5)문자열의 갯수가 5일 때

asdsdftktfdsdsa -> asd+sdf+tkt+fds+dsa -> 역순1+ 역순2+ 스스로 회문 + 역순2 + 역순1

 

즉 1) 문자열의 갯수가 1일 때 = 스스로 회문

        문자열의 갯수가 홀수 일 때 = 역순+회문+역순의 구조

        문자열의 갯수가 짝수 일 때 = 역순+역순의 구조인 것을 알 수 있다. 

 

결국 문자열을 스스로 회문인 가 아닌가 판단하고,

문자열이 서로 역순인가 아닌가 판단하면 된다.

 

그러다, 조건을 보지 못하고 머릿 속이 뒤죽박죽해졌다.

 

문자열마다 길이가 다를 수 있는데 팰런트롬의 최대 길이는 어떻게 구하지?

=>문자열의 길이는 서로 같다.란 조건이 있다.

 

스스로 회문이면서 다른 문자열이랑 역순인 것은?

=>주어진 모든 문자열은 서로 다르다.

 

나랑 역순인 애가 또 있으면?

=>주어진 모든 문자열은 서로 다르다.

 

2. 디테일한 구현

서로 역순인 문자열은 cp 리스트에 튜플 형태로 저장한다.

->조건에서 주어진 모든 문자열은 서로 다르다 했으므로

   중복 없이 저장 된다.

 

스스로 회문인 문자열은 self_arr 리스트에 저장한다.

->조건에서 주어진 모든 문자열은 서로 다르다 했으므로

   중복 없이 저장 된다.

   (물론, 서로 역순인 문자열도 없다.)

 

서로 역순인 문자열 cp는

기본적으로 2개씩 짝지어져 있기에 짝수이고

들어가있는 모든 원소를 조합할 수 있다.

왜냐하면 중복이 없고 기본적으로 짝이 있는 형태이기 때문이다.

 

ex) 역순1 역순2 역순 3 ... 역순 n 역순 n ... 역순3 역순2 역순1

 

4가지 경우가 있다.

1) 문자열의 조합 갯수가 짝수

    팰런트롬의 크기=서로 역순인 문자열을 담은 리스트의 크기*2*문자열의 길이

 

2) 문자열의 조합 갯수가 홀수(조합 갯수가 1보다 클 때) 

    팰런트롬의 크기=서로 역순인 문자열을 담은 리스트의 크기*문자열의 길이+문자열의 길이

 

3) 문자열의 조합 갯수가 1일때

    팰런트롬의 크기= 문자열의 길이

 

4) 팰런트롬 존재 x

    팰런 트롬의 크기=0

 

1) cp(서로 역순인 문자열을 담은 리스트)의 크기가 1 이상, s_self(스스로 회문인 문자열)의 크기가 1이상

    팰런트롬의 최대 크기=len(cp)*2*m+m

 

2) cp의 크기가 1 이상, s_self의 크기가 0

   팰런트롬의 최대 크기=len(cp)*2*m

 

3)cp의 크기가 0이고, s_self의 크기가 1 이상

  팰런트롬의 최대 크기=m

 

4) 둘 다 크기가 0

  팰런트롬의 최대 크기=0

 

3. 코드 구현

def self_reverse(s):
    for i in range(0,len(s)//2):
        if s[i]!=s[len(s)-1-i]:
            return False
    return True
 
def couple(x,y):
    if x[::-1]==y[::]:
        cp.append((x,y))
 
if __name__=='__main__':
 #  sys.stdin=open('input2.txt','r')   
    
    
    t=int(input()) ## 총 테스트 케이스 개수
    
    for tc in range(t):
       n,m=map(int,input().split()) ##n=주어지는 문자열의 갯수,m=문자열의 길이
 
       s_arr=[] ##문자열을 담는 배열
       s_self=[] ##스스로 회문인 문자열을 담는 배열
       cp=[] ##서로 역순인 문자열을 담는 배열
       for i in range(n):
          s_arr.append(input()) ##문자열을 넣는다.
     
       for s in s_arr:
           if self_reverse(s):
               s_self.append(s)
      
       for i in range(0,len(s_arr)-1):
           for j in range(i+1,len(s_arr)):
               couple(s_arr[i],s_arr[j])
 
       if len(cp)>0 and len(s_self)>=1:
            res=len(cp)*2*m+m
       elif len(cp)>0 and len(s_self)==0:
            res=len(cp)*2*m
 
       elif len(cp)==0 and len(s_self)>=1:
             res=m
       else:
             res=0
 
       print(f'#{tc+1} {res}')

 

 

 

4. 깨달은 점 및 반성

1.문제에 주어진 조건을 잘 보자

=>'주어진 모든 문자열은 서로 다르다.'

    '문자열의 길이는 모두 같다.'

   ->위 조건을 보지 못했을 땐, 멘붕이었다.

 

2.쫄지 말자

=>이번 문제까지 D3 난이도는 7문제 밖에 안 풀어봤지만,

   조건이 정말 더럽거나 복잡한 문제는 없는 것 같다.

 

3.역시나 조건이 1일때부터 n까지 차근차근 살펴보자

->문제 풀이의 해법이 보이기 시작한다.