[SWEA - D3] 1216. 회문2

가장 긴 회문의 길이를 구하는 문제

 

 

나의 코드 

for _ in range(10):
    t = int(input())
    arr = []
    result = 0
    for _ in range(100):
        arr.append(input())
        
    for i in range(100):
        b = [x[i] for x in arr]
        for j in range(100):
            for length in range(1,101):
                if j+length > 100:
                    break
                tmp1 = arr[i][j:j+length]
                tmp2 = b[j:j+length]
                if  tmp1 == tmp1[::-1] and length > result:
                    result = length
                if  tmp2 == tmp2[::-1] and length > result:
                    result = length

    print("#"+str(t) ,result )

 

3중 for 문 써서 시간 초과 나올 줄 알았는데 통과 

 

보통 1-5초 시간제한인데 SWEA 문제는 파이썬의 경우 30초 제한이다. 

 

시간복잡도 생각안하고 pass 를 목적으로 한다면 이렇게 풀어도 되려나,,?

 

 

다른 풀이보면 시간복잡도를 줄이기 위해 

맨 처음 문자열의 양 끝 값이 같을 때만 안쪽 확인하기 -> 다르면 break