[SWEA D3] 1216. [S/W 문제해결 기본] 3일차 - 회문2 (파이썬)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&passFilterYn=Y&contestProbId=AV14Rq5aABUCFAYi&categoryId=AV14Rq5aABUCFAYi&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=P&pageSize=10&pageIndex=2

SW Expert Academy

 

문제

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

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

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

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

 

제약사항

• 각 칸의 들어가는 글자는 c언어 char type으로 주어지며 'A', 'B', 'C' 중 하나이다.ABA도 회문이며, ABBA도 회문이다. A또한 길이 1짜리 회문이다.즉, 아래 예에서 노란색 경로를 따라가면 길이 7짜리 회문이 되지만 직선이 아니기 때문에 인정되지 않는다.
• 가로, 세로 각각에 대해서 직선으로만 판단한다.
• 글자 판은 무조건 정사각형으로 주어진다.

 

입력

각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.

총 10개의 테스트케이스가 주어진다.

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 찾은 회문의 길이를 출력한다.

Solution

input().strip() : 띄어쓰기 없이 받은 문자열을 한개씩 읽어옴
list(zip(*arr1)): 전치 행렬(행과 열을 자리 바꿈)로 바꿈

 

회문의 최댓값을 찾는 문제이기에 회문의 길이가 100부터 시작해 1씩 감소하며 해당하는 회문이 있으면 true를 리턴하도록 구현했다.

 

=> 존재하는지의 여부를 함수로 구현하여 확인하는게 더 간단할 수 있다는 걸 생각하면서 풀자!

def pal(arr,leng):
        for i in arr:
            for j in range(100-leng+1):
                if i[j:j+leng] ==i[j:j+leng][::-1]:
                    return True
        return False

for test_case in range(1, 11):
    N = int(input())
    n =100
    arr1= [list(input().strip()) for _ in range(100)]
    arr2 =list(zip(*arr1))
    
    for leng in range(n,1,-1):
        if pal(arr1,leng) or pal(arr2,leng):
            break
    print(f'#{N} {leng}')