[SWEA] 1216. 회문2 - Python

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14Rq5aABUCFAYi&categoryId=AV14Rq5aABUCFAYi&categoryType=CODE&problemTitle=%ED%9A%8C%EB%AC%B82&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

< 📝 문제 >

"기러기" 또는 "level"과 같이 거꾸로 읽어도 제대로 읽은 것과 같은 문장이나 낱말을 회문(回文, palindrome)이라 한다.

주어진 100x100 평면 글자판에서 가로, 세로를 모두 보아 가장 긴 회문의 길이를 구하는 문제이다.

위와 같은 글자 판이 주어졌을 때, 길이가 가장 긴 회문은 붉은색 테두리로 표시된 7칸짜리 회문이다.

예시의 경우 설명을 위해 글자판의 크기가 100 x 100이 아닌 8 x 8으로 주어졌음에 주의한다.

< ❓ 생각 >
회문의 길이가 정해져 있지 않고 가장 긴 회문의 길이를 구하는 것이므로 회문의 길이를 하나하나 줄여가며 회문이 있는지 찾아보기

1. 가로회문

 1) 구간 M에서 양 끝 값이 같을 때만 안쪽 확인

 2) 안쪽 확인 - 다르면 break / 모두 같으면 가장 긴 회문이므로 True 반환

2. 세로회문

 1) 구간 M에서 양 끝 값이 같을 때만 안쪽 확인

 2) 안쪽 확인 - 다르면 break / 모두 같으면 가장 긴 회문이므로 True 반환

3. 구간 M일 때 가로회문, 세로회문 둘 다 없으면 구간 M-1 => 1번으로

 

< 💻 코드 >

# M : 회문 길이, arr : 리스트
# 회문 있으면 True, 없으면 False
def palindrome(M, arr):
    for i in range(100):
        # 가로 회문
        for j in range(0, 100-M+1):
            # 구간 M에서 양 끝 값이 같을 때만 안쪽 확인
            if arr[i][j] == arr[i][j+M-1]:
                # 안쪽 확인
                # 다르면 멈추기
                # 모두가 같으면 True 반환
                for k in range(1, M//2):
                    if arr[i][j+k] != arr[i][j+M-1-k]:
                        break
                else:
                    return True

        # 세로 회문
        for j in range(0, 100-M+1):
            if arr[j][i] == arr[j+M-1][i]:
                for k in range(1, M//2):
                    if arr[j+k][i] != arr[j+M-1-k][i]:
                        break
                else:
                    return True
    return False

T = 10
for tc in range(1,T+1):
    # N : 테스트 케이스의 번호, arr : 테스트 케이스
    N = int(input())
    arr = [list(input()) for _ in range(100)]
    # M : 회문의 길이
    for M in range(100, -1, -1):
        # 회문 있으면 True, 그 때 M이 회문의 최대 길이
        if palindrome(M, arr):
            print(f'#{tc} {M}')
            break