문제

문제 바로가기

문자열을 뒤집어도 문자열이 동일하다면 그걸 팰린드롬이라 한다했다

1. N개의 길이가 같은 문자열이 주어진다
2. 몇개의 문자열을 고른 후 고른 문자열들을 재배열해서 순서대로 합쳤을때 최종 팰린드롬의 길이가 최대화 되어야한다

접근하기

1. 문자열을 합칠 때 aab, baa 이렇게 두 문자가 있으면 합쳤을때 팰린드롬이 된다
2. racecar, abcdcba 이렇게 그 문자가 팰린드롬 자체이면 합쳤을때 팰린드롬이 되지 않는다
3. 문자열을 뒤집었을때의 문자열이 있는지 확인하고, 팰린드롬 자체인 문자열이 있는지 확인한다

풀이

T = int(input())

for t in range(1,T+1):
    n,m = map(int,input().split())
    a_arr = []
    answer1 = 0 
    answer2 = 0

    for _ in range(n):
        arr = input()
        a_arr.append(arr)
    
    for a in a_arr:
   		 #문자열의 역순이 리스트에 있고 그게 자기자신이 아닐때
        if a[::-1] in a_arr and a != a[::-1]:
            answer1 += m
        #문자열의 역순이 자기자신일때
        elif a[::-1] in a_arr:
            answer2 = m
    
    print(f'#{t} {answer1+answer2}')