[Python | SWEA] 1216. [S/W 문제해결 기본] 3일차 - 회문2

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

문제

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

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

 

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

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

 

 

 

제출 답안

 

개선 답안

전체 문장의 회문을 검사하는 게 아니라,

문장의 끝과 끝부터 하나씩 같은 지 검사

def is_pal_idx(arr, leng):
    for lst in arr:
        for i in range(N-leng+1):  # i는 모든 시작위치
            for j in range(leng//2):    # 몇 개를 검사
                if lst[i+j] != lst[i+leng-1-j]:
                    break       # 다음 위치로
            else:
                # for문이 break없이 끝까지 실행되었을 시 else 실행됨
                return True
    return False

for test_case in range(1, 11):
    _ = int(input())
    N = 100
    arr1 = list(input() for _ in range(N))
    arr2 = ["".join(x) for x in zip(*arr1)]
    
    for leng in range(N, 1, -1):    # 찾으면 최대값
        if is_pal_idx(arr1, leng) or is_pal_idx(arr2, leng):
            break
    print(f"#{test_case} {leng}")

 

참고 자료

https://www.youtube.com/watch?v=nAA_3fbwsZw