SWEA 4861 회문 (python)

4861. [파이썬 S/W 문제해결 기본] 3일차 - 회문

 

[파이썬 S/W 문제해결 기본] 3일차 문제

2021.05.17 - [Algorithm] - SWEA 4861 회문 (python)

2021.05.17 - [Algorithm] - SWEA 4864 문자열 비교 (python)

2021.05.17 - [Algorithm] - SWEA 4865 글자수 (python)

 

문제

ABBA처럼 어느 방향에서 읽어도 같은 문자열을 회문이라 한다. NxN 크기의 글자판에서 길이가 M인 회문을 찾아 출력하는 프로그램을 만드시오.

회문은 1개가 존재하는데, 가로 뿐만 아니라 세로로 찾아질 수도 있다.

예를 들어 N=10, M=10 일 때, 다음과 같이 회문을 찾을 수 있다.

G	O	F	F	A	K	W	F	S	M
O	Y	E	C	R	S	L	D	L	Q
U	J	A	J	Q	V	S	Y	Y	C
J	A	E	Z	N	N	Z	E	A	J
W	J	A	K	C	G	S	G	C	F
Q	K	U	D	G	A	T	D	Q	L
O	K	G	P	F	P	Y	R	K	Q
T	D	C	X	B	M	Q	T	I	O
U	N	A	D	R	P	N	E	T	Z
Z	A	T	W	D	E	K	D	Q	F

 

[입력]

첫 줄에 테스트 케이스 개수 T가 주어진다. 1≤T≤50

다음 줄부터 테스트케이스의 첫 줄에 N과 M이 주어진다. 10≤N≤100, 5≤M≤N

다음 줄부터 N개의 글자를 가진 N개의 줄이 주어진다.

 

[출력]

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

 

코드

T = int(input())

# 거꾸로 뒤집어 주는 함수
def my_reverse(line):
    # 거꾸로 뒤집어줄 값 초기화
    r_line = []
    # 뒤에서 부터 불러오면서 리스트에 더해줌
    for i in range(len(line)-1, -1, -1):
        r_line.append(line[i])
    # 거꾸로 반영된 리스트 반환
    return r_line

# 회문을 하는 함수
def palindrome(N, M, words):
    # 전체 크기가 N
    for i in range(N):
        # 가로검사
        for j in range(N-M+1):
            # 가로 세로 문장이 들어갈 리스트 초기화
            row = []
            col = []
            # 지정된 길이만큼의 가로 세로 문장을 각각 만들어줌
            for k in range(M):
                row.append(words[i][j+k])
                col.append(words[j+k][i])
            # 만약 회문을 찾았다면 1개만 존재하므로 바로 리턴
            if row == my_reverse(row):
                return row
            elif col == my_reverse(col):
                return col

for tc in range(1, T+1):
    N, M = map(int, input().split())
    words = [list(input()) for _ in range(N)]
    # 원하는 형식으로 출력하기 위해 join 사용
    result = ''.join(palindrome(N, M, words))
    print("#{} {}".format(tc, result))