[swea 1216-파이썬]회문2

swea 1216 회문2

사용언어 : PYTHON

풀이

시간복잡도를 줄이기 위해 길이가 1인 문장부터 오름차순으로 100까지 검사하는 것이 아닌

100부터 내림차순으로 검사를 해야한다.

내림차순으로 검사를 수행하다가 그 문장이 회문이 맞다면 가장 긴 회문이 되기 때문이다.

행 방향으로 가장 긴 회문의 길이와 열 방향으로 가장 긴 회문의 길이 중 더 큰 값이 정답이 된다.

총 세 개의 함수를 이용하였다.

• 회문인지 확인하는 check함수

• 행 방향으로 탐색하는 find_row함수

• 열 방향으로 탐색하는 find_col함수 (함수 안에서 find_row를 호출하고 크기를 비교한 뒤 최종 정답을 return함)

코드

def check(st):

    for i in range(len(st)//2):
        if st[i]!=st[len(st)-1-i]:
            return False

    return True

def find_row():

    answer=1

    for p in range(100,0,-1):
        for q in range(0,101-p):
            for r in range(0,100):
                st=l[r][q:q+p]
                if check(st): # 회문이 맞다면 가장 긴 회문이 되므로 return을 수행
                    answer=len(st)
                    return answer


def find_col():
    transpose_l=list(zip(*l)) # 열 방향으로 탐색하기 위해 전치행렬을 구함

    answer=find_row()

    for p in range(100,0,-1):
        for q in range(0,101-p):
            for r in range(0,100):
                st=transpose_l[r][q:q+p]
                if check(st):
                    if len(st)>answer:
                        answer=len(st)
                    return answer


for _ in range(10):

    N=int(input())
    l=[list(input()) for _ in range(100)]


    print('#{} {}'.format(N,find_col()))