[Python] 팰린드롬 문제 (SWEA D3 19003번 파이썬)

어떠한 문자열 S 가 뒤집어도 S와 동일하다면 S 를 팰린드롬 이라고 하자. 
양의 정수 N, 그리고 N 개의 길이가 같은 문자열이 주어졌을 때, 이들 중 몇 개의 문자열을 고른 후, 
고른 문자열들을 적당히 재배열해서 (문자열을 재배열하는 것이고, 문자열 내부 문자의 순서는 바꿀 수 없다)  순서대로 합쳤을 때 팰린드롬이 되게 해야 한다. 

이 때 최종 팰린드롬의 길이를 최대화해라.

[입력]
첫 번째 줄에 테스트 케이스의 수 TC가 주어진다. 이후 TC개의 테스트 케이스가 새 줄로 구분되어 주어진다. 각 테스트 케이스는 다음과 같이 구성되었다.
첫 번째 줄에 문자열의 개수, 그리고 각 문자열의 길이를 나타내는 두 정수 N, M 이 주어진다. (1≤N≤100, 1≤M≤50)
이후 N 개의 줄에 알파벳 소문자로만 이루어진 길이 M 의 문자열이 주어진다. 주어진 모든 문자열은 서로 다르다. 

[출력]
각 테스트 케이스 마다 한 줄씩 최대화된 팰린드롬의 길이를 출력하라.

 

---

 

 

처음에 단순 완전탐색 문제로 생각해 순열로 해결하려 했으나, 해결되지 않는 케이스가 있어서 다시 접근했습니다.

이후 완전탐색으로 해결할 수 있었습니다.

 

 

문제의 핵심은 팰린드롬인 문자열을 하나만 체크한다는 것입니다.

팰린드롬 문자가 아무리 많아도, 여러 문자열을 조합해서 팰린드롬 문자열을 만들기 위해선

가운데에 팰린드롬 수가 하나만 존재해야 합니다. (같은 문자가 주어지는 경우는 없기 때문)

 

다시 말해서 팰린드롬 문자가 없거나 있는 경우로 나눠야 하고,

없는 경우는 그냥 이후 완전탐색으로 넘어가면 되지만,

있는 경우엔 팰린드롬 문자 하나만 사용한다고 가정하고 answer에 m을 더하고 시작해야 합니다.

 

 

def is_pal(s:str):
    return s[::-1]

 

우선 문자열을 팰린드롬으로 만들기 위한 함수를 정의하고 시작합니다.

 

 

    arr = []
    pal = []
    for i in range(n):
        s = input()
        if s==s[::-1]:
            pal.append(s)
        else:
            arr.append(s)

 

입력받은 문자열을 팰린드롬인 수(pal)와 팰린드롬이 아닌 수(arr)로 나눠줍니다.

 

 

if len(pal) >= 1:
        answer += m
leng = len(arr)
for i in range(leng-1):
    for j in range(i+1, leng):
        if is_pal(arr[i]) == arr[j]:
            answer += 2*m

 

가장 중요한 부분입니다.

팰린드롬수가 하나라도 있으면 무조건 m을 누적합니다.

 

이후 팰린드롬이 아닌 나머지 문자들을 완전탐색을 통해 조합해서 쌍을 만듭니다.

앞서 작성한 팰린드롬 반환 함수를 통해 확인합니다.

두 문자열이 팰린드롬일 경우 문자열의 길이*2를 추가로 누적해줍니다.

 

이렇게 하는 이유는 만약  aab, baa ,ccb, bcc가 있다면 결과적으로 팰린드롬이 돼야하므로 쌍을 이뤄야합니다.

쌍을 이룬다는 것은 두 개가 팰린드롬을 이라는 것을 말합니다.

 

 

 

전체 코드

#swea 19003 팰린드롬 문제

def is_pal(s:str):
    return s[::-1]

T = int(input())
for t in range(1,1+T):
    n, m = map(int, input().split())
    arr = []
    pal = []
    for i in range(n):
        s = input()
        if s==s[::-1]:
            pal.append(s)
        else:
            arr.append(s)
    answer = 0
    if len(pal) >= 1:
        answer += m
    leng = len(arr)
    for i in range(leng-1):
        for j in range(i+1, leng):
            if is_pal(arr[i]) == arr[j]:
                answer += 2*m
    print(f"#{t} {answer}")

    #팰린드롬이 아무리 많아도 어짜피 한 개 밖에 못씀 -> answer에 m 누적
    #팰린드롬이 아닌 수 중에서 뒤집으면 같은 문자열 두 개를 찾아서 answer에 m*2 누적
    # -> 이렇게 하는 이유는 aab, baa ,ccb, bcc 가 있으면 결과적으로 팰린드롬이 돼야하므로
    #쌍을 이뤄야함. 쌍을 이룬다는 것은 두 개의 역이 같은지를 확인하는 것