[SWEA] 4861. 회문 - Python

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

< 📝 문제 >

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

< ❓ 생각 >
1. 덩어리로 비교

회문이 1개 존재

M크기의 배열이 뒤집었을 때와 같으면 회문

 

2. 각 요소요소 확인

회문이 1개 존재

 1) 가로회문 먼저 확인 - > 같으면 안쪽 요소 계속 확인 / 다르면 첫 번째 문자를 다시 지정 or 다음 행

 2) 가로 회문 없으면 세로 회문 존재

 

< 💻 코드 >
1.

# 덩어리로 비교하기
def a(N,M,arr):
    k = 0
    for i in range(N):
        for k in range(N-M+1):
            # 가로 회문
            h = arr[i][k:k+M]
            # 세로 회문
            v = [arr[j][i] for j in range(k,k+M)]
            # 자신과 자신을 뒤집은 것이 같다면 회문
            if h == h[::-1]:
                return h
            if v == v[::-1]:
                return v

# T : 테스트 케이스 개수
T = int(input())
for tc in range(1,T+1):
    # N : N*N 크기의 글자판, M : 회문의 길이
    N, M = map(int,input().split())
    # arr : 글자판
    arr = [list(input()) for _ in range(N)]

    result = a(N,M,arr)
    print(f'#{tc}',''.join(result))

2.

def a(N, M, arr):
    # 가로 또는 세로의 길이가 M인 회문 찾기
    # 가로 회문 찾기
    i = 0
    j = 0
    k = 0
    result = []
    while i < N:
        if M - 1 - j + k < N:
            # 같으면 안쪽도 확인
            if arr[i][j + k] == arr[i][M - 1 - j + k]:  
                j += 1
            # 다르면 첫번째 문자를 다시 지정
            else:  
                j = 0
                k += 1
        # 다음 행 확인
        else:
            i += 1
            k = 0

        # 회문일 때
        if j == M // 2:
            result = arr[i][k:k + M]
            return result

    # 가로 회문 없으면 세로 회문 찾기
    i = 0
    j = 0
    k = 0
    while i < N:
        if M - 1 - j + k < N:
            # 같으면 안쪽도 확인
            if arr[j + k][i] == arr[M - 1 - j + k][i]:  
                j += 1
            # 다르면 첫번째 문자를 다시 지정
            else:  
                j = 0
                k += 1
        # 다음 행 확인
        else:
            i += 1
            k = 0

        # 회문일 때
        if j == M // 2:
            for s in range(k,k+M):
                result += arr[s][i]
            return result

# T : 테스트 케이스 개수
T = int(input())
for tc in range(1,T+1):
    # N : N*N 크기의 글자판, M : 회문의 길이
    N, M = map(int,input().split())
    # arr : 글자판
    arr = [list(input()) for _ in range(N)]

    result = a(N,M,arr)

    print(f'#{tc}',''.join(result))

< ❗ >

회문 크기가 정해져 있을 때 덩어리로 비교하는 것이 더 쉽다. 다만 크기가 정해져 있지 않다면 길이를 점점 줄여가면서 확인해볼 수 있다.