SWEA 4861 회문 (palindrome)

문제 출처 : SW Expert Academy

문제정리

회문 찾기 (앞으로 해도 뒤로해도 이효리 같은 느낌..)

J A E Z N N Z E A J -> 회문 

n x n 인 글자판에서 길이가 m인 회문찾기
※ 주의 : 가로 뿐만아니라 세로도 찾아질수 있다! 

문제풀이

1. 뒤집기 함수   : range(list, -1, -1) 로 거꾸로 불러오기 
    - 세로배열은 인덱싱[::-1]을 통해 찾을 수 없음을 주의
    
2. 회문찾기 함수 : 순 배열과 역 배열 비교를 통해 찾기
    - 세로 리스트은 같은 열에 행인덱스만 바꿔가며 추가

1. 문자열 뒤집기 함수

def reverse(row):
    # 리스트 초기화
    r_row = []
    # 거꾸로 불러오며 리스트에 더하기
    for i in range(len(row)-1, -1, -1):
        r_row.append(row[i])
    # 뒤집힌 리스트 반환
    return r_row

2. 회문(팰린드롬) 함수

def palindrome():
    for i in range(n):
        # 가로 검사
        for j in range(n-m+1):
            tmp = words[i][j:j+m]
            # 회문검사
            if tmp == reverse(tmp):
                return tmp
        # 세로 검사 
        for j in range(n-m+1):
            tmp = [] # 세로문자열을 위한 빈리스트
            for k in range(m):
                tmp.append(words[j+k][i]) # k값이 증가하며 세로값 추가
            if tmp == reverse(tmp):
                return tmp            
    return [] # 팰린드롬이 없으면 빈리스트 반환

3. 함수적용

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