문제 출처 : [SWEA] 4861 회문
learn -> course -> programming intermediate -> string -> 회문

문제

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

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

입력

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

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

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

출력

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

코드

T = int(input())
for tc in range(1, T + 1):
    # N : 글자판의 크기, M : 회문의 길이
    N, M = map(int, input().split())
    str_list = [list(input()) for _ in range(N)]    # 주어진 글자판을 2차원 리스트로 받아옴
    result_words = ''       # 회문을 저장할 문자열
    words_idx = [0, 0]      # 회문의 인덱스 값을 저장할 리스트

    # 가로줄 탐색
    for i in range(N):
        for num in range(N - M + 1):
            words = ''      # 회문의 절반을 저장할 문자열
            cnt = 0         # 양쪽의 문자열이 같은 경우 cnt + 1
            # 회문의 절반만큼 반복
            for j in range(M // 2):
                # 회문의 앞쪽 값과 뒷쪽 값을 서로 비교
                if str_list[i][num + j] == str_list[i][j + M - 1 + num - j * 2]:
                    cnt += 1        # 양쪽 값이 일치할 경우 + 1
                    words += str_list[i][num + j]       # 회문의 절반을 저장하기 위해 현재 문자열을 저장
                    words_idx[0], words_idx[1] = i, num + j     # 회문의 절반 중 마지막 인덱스를 저장
            # 양쪽 값이 일치하는 경우가 회문의 절반과 같을 경우
            if cnt == M // 2:
                result_words = words    # 회문을 저장할 문자열에 앞서 구한 회문의 앞부분을 저장
                # 회문의 길이가 홀수인 경우
                if M % 2 == 1:
                    # 앞서 저장해둔 words의 마지막 인덱스 + 1한 위치의 문자열을 결과를 저장할 문자열에 추가
                    result_words += str_list[words_idx[0]][words_idx[1] + 1]
                # words를 뒤에서부터 순회하면서 결과값에 추가
                for k in range(M // 2 - 1, -1, -1):
                    result_words += words[k]
                print('#{} {}'.format(tc, result_words))

    # 세로줄 탐색
    for i in range(N):
        for num in range(N - M + 1):
            words = ''
            cnt = 0
            # 회문의 절반만큼 반복
            for j in range(M // 2):
                # 회문의 앞쪽 값과 뒷쪽 값을 서로 비교
                if str_list[num + j][i] == str_list[j + M - 1 + num - j * 2][i]:
                    # 양쪽 값이 일치하면 cnt + 1, words에 문자열 저장, 인덱스 저장
                    cnt += 1
                    words += str_list[num + j][i]
                    words_idx[0], words_idx[1] = num + j, i
            # 양쪽 값이 일치하는 경우가 회문의 절반과 같을 경우
            if cnt == M // 2:
                result_words = words
                # 회문의 길이가 홀수인 경우
                if M % 2 == 1:
                    result_words += str_list[words_idx[0] + 1][words_idx[1]]
                # words를 뒤에서부터 순회하면서 결과값에 추가
                for k in range(M // 2 - 1, -1, -1):
                    result_words += words[k]
                print('#{} {}'.format(tc, result_words))

풀이 방법

가로줄과 세로줄을 따로 탐색하여 회문을 찾았다. 우선 가로줄의 경우 전체 길이 - 회문의 길이만큼 반복하면서 회문을 탐색하였는데 회문의 경우 앞, 뒤의 문자가 같기 때문에 회문 길이의 절반만큼만 반복되도록 하였다. 그래서 문자열의 앞, 뒤가 같을 경우 절반의 문자열을 다시 뒤에서부터 순회하면서 이어붙여주었다. 세로줄도 가로줄과 마찬가지로 작성하였다.