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

출처 : 링크텍스트

1. 풀이방법

회문을 판별하는 기초적인 알고리즘이다. for문을 여러번 중첩하여 가장 긴 회문을 찾는다.

2. 코드

첫 번째 방법

def palindrome(string):
    n = len(string)
    for s in range(n // 2):
        if string[s] != string[n - 1 - s]:
            return 0
    return 1


for tc in range(10):
    T = int(input())
    arr = [list(map(str, input())) for _ in range(100)]
    length = 1
    word = ''
    for i in range(100):  # 행 번호
        for j in range(length, 101):  # 회문 길이
            for k in range(101 - j):  # 열 번호
                for m in range(k, k + j): # 단어를 저장
                    word += arr[i][m]
                if palindrome(word):
                    temp = len(word)
                    if length < temp:
                        length = temp
                else:
                    word = ''
    for i in range(100):  # 열 번호
        for j in range(length, 101):  # 회문 길이
            for k in range(101 - j):  # 행 번호
                for m in range(k, k + j): # 단어를 저장
                    word += arr[m][i]
                if palindrome(word):
                    temp = len(word)
                    if length < temp:
                        length = temp
                else:
                    word = ''
    print('#{0} {1}'.format(T, length))

생각나는데로 막 풀어서 나온 결과이다. 결괏값은 정확하게 나왔지만 소요시간이 매우 오래걸려 이를 개선할 필요를 느껴 어느 부분에서 시간이 오래걸리는지 찾았다.

두 번째 방법

def palindrome(string):
    length = 1
    for i in range(100):  # 행 번호
        for j in range(length, 101):  # 회문 길이
            for k in range(101 - j):  # 열 번호
                word = string[i][k: k + j]
                if word == word[::-1]:
                    temp = len(word)
                    if length < temp:
                        length = temp
    return length


for tc in range(10):
    T = int(input())
    arr = [list(map(str, input())) for _ in range(100)]
    trans_arr = list(map(list, zip(*arr)))
    row = palindrome(arr)
    col = palindrome(trans_arr)
    print('#{0} {1}'.format(T, max(row, col)))

단어를 일일이 찾아 저장하는 과정에서 시간이 많이 소요되었다는 점을 찾아내어 사용자 함수를 만들고 단어를 슬라이싱을 통해 만들어 회문을 판별하였다.시간이 많이 줄었지만 생각보다 많이 줄지 않았고 슬라이싱을 사용한 점이 마음에 들지 않아 다시 생각해 보았다.

세 번째 방법

for tc in range(10):
    T = int(input())
    arr = [input() for _ in range(100)]
    max_result = 0
    length = 0
    for i in range(100): # 행 번호
        for j in range(100, length, -1): # 회문 길이
            result = 0
            for k in range(101 - j): # 열번호
                if result:
                    break
                for m in range(j): # 회문 판별
                    if arr[i][k + m] == arr[i][k + j - m - 1]:
                        result += 1
                    else:
                        result = 0
                        break
                if max_result < result:
                    max_result = result
                    length = result
    for i in range(100): # 열 번호
        for j in range(100, length, -1): # 회문 길이
            result = 0
            for k in range(101 - j): # 행 번호
                if result:
                    break
                for m in range(j): # 회문 판별
                    if arr[k + m][i] == arr[k + j - m - 1][i]:
                        result += 1
                    else:
                        result = 0
                        break
                if max_result < result:
                    max_result = result
                    length = result

    print('#{0} {1}'.format(T, max_result))

굳이 단어를 저장해가며 회문인지 판별할 필요 없이 단순히 판별만 하면 되었다. 너무 어렵게 생각한 것이 시간이 많이 소요되게 한 원인이었다.