회문 Python(SW Expert Academy)

난이도 : D2

문제번호 : 4861

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVGOEKqeoDFAWg#

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

ABBA처럼 어느 방향에서 읽어도 같은 문자열을 회문이라 한다. NxN 크기의 글자판에서 길이가 M인 회문을 찾아 출력하는 프로그램을 만드시오. 회문은 1개가 존재하는데, 가로 뿐만 아니라 세로로 찾아질 수도 있다.   예를 들어 N=10, M=10 일 때, 다음과 같이 회문을 찾을 수 있다.

입력

첫 줄에 테스트 케이스 개수 T가 주어진다.  1≤T≤50 다음 줄부터 테스트케이스의 첫 줄에 N과 M이 주어진다. 10≤N≤100, 5≤M≤N 다음 줄부터 N개의 글자를 가진 N개의 줄이 주어진다.

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예시

입력

출력

3 10 10 GOFFAKWFSM OYECRSLDLQ UJAJQVSYYC JAEZNNZEAJ WJAKCGSGCF QKUDGATDQL OKGPFPYRKQ TDCXBMQTIO UNADRPNETZ ZATWDEKDQF 10 10 WPMACSIBIK STWASDCOBQ AMOUENCSOG XTIIGBLRCZ WXVSWXYYVU CJVAHRZZEM NDIEBIIMTX UOOGPQCBIW OWWATKUEUY FTMERSSANL 20 13 ECFQBKSYBBOSZQSFBXKI VBOAIDLYEXYMNGLLIOPP AIZMTVJBZAWSJEIGAKWB CABLQKMRFNBINNZSOGNT NQLMHYUMBOCSZWIOBINM QJZQPSOMNQELBPLVXNRN RHMDWPBHDAMWROUFTPYH FNERUGIFZNLJSSATGFHF TUIAXPMHFKDLQLNYQBPW OPIRADJURRDLTDKZGOGA JHYXHBQTLMMHOOOHMMLT XXCNJGTXXKUCVOUYNXZR RMWTQQFHZUIGCJBASNOX CVODFKWMJSGMFTCSLLWO EJISQCXLNQHEIXXZSGKG KGVFJLNNBTVXJLFXPOZA YUNDJDSSOPRVSLLHGKGZ OZVTWRYWRFIAIPEYRFFG ERAPUWPSHHKSWCTBAPXR FIKQJTQDYLGMMWMEGRUZ

#1 JAEZNNZEAJ #2 MWOIVVIOWM #3 TLMMHOOOHMMLT

---

2. 문제풀이

파이썬 3일차 연습문제 중 하나인 회문 문제이다. 회문은 여러가지 방식으로 풀 수가있다. 단순하게 회문 함수를 만들어서 풀수도 있고 파이썬의 in 함수를 이용하여 풀 수도있고, kmp 알고리즘을 직접 구현하여 풀 수도있다. 나는 간단하게 in함수를 이용하여 풀었다. 가로 세로에서 회문을 찾는것이기 때문에 가로 리스트와 세로리스트를 만들어서 편하게 계산했다. 탐색을 할때는 특정 길이만큼 추출하여 뒤집은 다음에 같은 무자열이 있는지 확인하는 방식으로 풀었다.

---

3. 소스코드

#D2 4861 회문
T = int(input())
for t in range(1, T+1):
    N, M = map(int, input().split())
    lst, lst2 = [], []
    #입력데이터 넣기
    for i in range(N):
        lst.append(input())
    #세로를 계산하기위해 세로데이터 넣기.
    for k in range(N):
        str_temp = ''
        for i in range(N):
            str_temp += lst[i][k]
        lst2.append(str_temp)
    result = ''
    #회문이기 때문에 뒤집어서 비교를 해본다.
    for k in range(N):
        temp, temp2 = list(lst[k]), list(lst2[k])
        temp.reverse()
        temp2.reverse()
        s_temp, s_temp2 = "".join(temp), "".join(temp2)
        #리스트안에 회문이 있다면 result에 저장한다.
        for i in range(N-M+1):
            if s_temp[i:M+i] in lst[k]:
                result = s_temp[i:M+i]
                break
            if s_temp2[i:M+i] in lst2[k]:
                result = s_temp2[i:M+i]
                break
    print("#{} {}".format(t, result))