팰린드롬 문제

풀이

문제를 보고 음... 재귀를 이용해서 완전탐색을 해볼까 하고 먼저 풀었다.

그렇게 아래 코드가 나왔다 하지만, 이러니까 답은 맞게 되는데 시간이 너무 오래 걸려서 제한시간 초과가 발생해버렸다.

def solution(s_list, visited, string):
    global max_length
    # 제일 큰 길이 확인
    if len(string) > max_length and string == string[::-1]:
        max_length = len(string)

    # 재귀로 확인
    for i in range(len(s_list)):
        if visited[i] == 0:
            visited[i] = 1
            a = string + s_list[i]
            solution(s_list, visited, a)
            visited[i] = 0
    return

T = int(input())
for testcase in range(1, T+1):
    max_length = 0
    N, M = map(int, input().split())
    s_list= []
    for _ in range(N):
        tmp_s = input()
        s_list.append(tmp_s)
        if max_length < len(tmp_s) and tmp_s == tmp_s[::-1]:
            max_length = len(tmp_s)
    visited = [0]* len(s_list)
    solution(s_list, visited, '')
    print(f'#{testcase} {max_length}')

그래서 고민에 고민에 고민을 하다가
아래의 방법을 이용했다.

리스트에 각 문자열을 넣은 리스트를 만들고 반복문을 돌린다.

해당 문자열의 역순인 것이 있다면, 길이를 더한다.(반복문이라서 나중에 또 한 번 보게 될 것이라서 2*M이 아니라 M만 더함)

또한 elif로 해당 문제열의 역순이 있는데 자기자신이라면, 그 것은 별개로 두도록한다.
결과에서 이 둘을 더하도록 한다.
뭐 이런 방식이다.

T=int(input())
for testcase in range(1, T+1):
    N,M=map(int,input().split())
    result1=0
    result2=0
    s_list=[]
    for _ in range(N):
        tmp_s = input()
        s_list.append(tmp_s)
    for w in s_list:
        # 문자열 역순, 그러니까 현재 문자열이 abc면 cba가 str_list에 있는지 확인.
        # 그리고 그게 회문인지 아닌지 확인하기
        if w[::-1] in s_list and w != w[::-1]:
            result1+=M
        # 문자열 역순이 str_list에 있냐? 그런데 그거 나임ㅋㅋㅋ 과 같은 상황일때
        elif w[::-1] in s_list:
            result2=M
     
    # 내 역순인 녀석들 abc면 cba, hijk면 kjih와 같은 녀석들은 result1
    # 나 홀로 회문이 가능한 녀석들은 reulst2
    
    # 답은 이것들을 길게 이어주는 일!
    print(f'#{testcase} {result1+result2}')