[SWEA][D3][#01216] 회문2

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

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

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

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

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

제약사항

각 칸의 들어가는 글자는 c언어 char type으로 주어지며 ‘A’, ‘B’, ‘C’ 중 하나이다.

글자 판은 무조건 정사각형으로 주어진다.

ABA도 회문이며, ABBA도 회문이다. A또한 길이 1짜리 회문이다.

가로, 세로 각각에 대해서 직선으로만 판단한다.

입력

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

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

출력

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

예제

입력

1
CCBBCBAABCCCBABCBCAAAACABBACCCCACAABCBBACACAACABCBCCB...
ACBAAAACCACCCBAACAAABACACCABCBCBABBBACBABCAACCBCCACBC...
CCCACCBCBACBACBCABAABABCCAAAACCCCCBBAABBCCBCCCABBACAC...
CABACBCBBCBABACABBBBBBABBCABCBCBCAABCBCCCBABACCCCABBA...
BCCBCCACCBCBCABBBCCABAACACCBCCCBCCACCBBCBCCCBBCCBACBC...
BBBBCBBAACABACCBCBCCABBBBCCAABCBBCACCBBCAAAABABABBABB...
ABBAACCCACBBABBABCCCABABCACABABACCCBACACABCBCCCBABCCC...
ABBBBAABCAACCBACBBAACACABCABACBAABCAABBCCCCCCACBCCCCA...
ACCACABABBACBBAACCBBACBBCCACCACCABCCBABABBBACBACBAABC...
BABACACCABCAACBAABCCACCACBCCAABBCBAABABAACAAAAAACCCBC...
...
2
CBBABBACCAACCCAABABAACCABCBBCCABABBBBBCCACBCCCCBBBAAC...
BBBCBACAAABAACACBCAABBAAABCABBBCAAACBAABCAAAAACBABBAB...
CAAAABCAABAACCBBABCCCACABABACBCCBCCBABABBCCCBCBACAAAC...
BBBACBBBBBAACBBCBABBCBAABACCCBBBBCCCBBBCABCABCAABCBCA...
ABBBBAABCBACCACBBCBBAABABCBCCAAABBCAAABBAABBCACABAABA...
ABCBACAAACCCAAABCACABBAABBCAACCBABCCACBABBBABAABAACBB...
ACACABCBAAACCACABABBCABCBABAAABCBCCABABCCAACACBCBABCA...
ACCBACACCAAAABABACABABBBBABBAABABBBBACBACABABACACACAA...
AAACCCCCBCAACCCCCAAAACBCACBBABBBBBABABBCCCCBBAACCBBCB...
CCABCCBBCAAAACACBBBBAAAACABACABCCCBACBABBACCAABAAACAB...

출력

#1 18
#2 17
...

My Sol

def Palindrome(lst):
    while (len(lst)>1):
        if lst[0]!=lst[-1]:
            return 0
        lst.pop(0)
        lst.pop(-1)
    return 1

def PalindromeLine(lst, N, max_l):
    for s in range(max_l, N):
        for j in range(0, N-s+1):
            if Palindrome(lst[j:j+s]):
                max_l = s
    return max_l

T = 10
for _ in range(T):
    tc = int(input())
    N = 100
    mat = [input() for _ in range(N)]

    max_l = 1
    for i in range(N):
        lstX = mat[i]
        now_l = PalindromeLine(lstX, N, max_l)
        if max_l < now_l:
            max_l = now_l

    for j in range(N):
        lstY = [mat[i][j] for i in range(N)]
        now_l = PalindromeLine(lstY, N, max_l)
        if max_l < now_l:
            max_l = now_l

    print(f'#{tc} {max_l}')

역시 2차원 배열에서의 회문이기 때문에 열을 우선으로 조회할지, 행을 우선으로 조회할지 결정하여 코드를 나누어 작성하면 되겠다. 우선 모든 행에 대해서 열을 반복해서 조회하는 방식부터 보겠다. 리스트를 전달받는 PalindromeLine() 함수를 정의하여 리스트를 전달해주는데, mat 2차원 배열은 어차피 1차원 리스트 행의 반복이므로 0부터 N-1까지 반복되는 i를 mat의 인덱스로 사용하여 한 번에 리스트를 구할 수 있다.

PalindromeList 함수는 max_l부터 s가 N-1까지 1씩 증가하는데 이는 회문인지 조회하는 영역의 길이를 의미하며, 아래에서 리스트에서 시작하는 지점의 인덱스 j는 0부터 N-s까지 하나씩 늘어나며 lst[j:j+s] 영역이 회문인지 조회하는 Palindrome() 함수에 대한 회문의 길이를 비교한다.

j가 0부터 N-s인 이유는 당연히 시작점은 처음점부터 시작함은 알 수 있을 것이고, 최대 인덱스가 j+s인데 s의 최대값이 N-1이므로 j는 N-s까지 되어야 N-1이라는 인덱스 범위를 넘지 않기 때문이다.

Palindrome 함수는 입력받은 리스트의 맨 앞과 맨 뒤의 값이 같다면 양 쪽의 텍스트를 떼어내는 방식인데, 길이가 2 미만, 즉 어떻게든 회문이 되는 상황이 되면 회문을 출력한다. 만약 양 쪽을 비교하는 과정에서 서로 일치하지 않는다면 회문이 아니므로 0을 반환하고 함수를 바로 끝내버린다.

이 방법이 효율적인 이유는 조회 영역이 길어지면 길어질수록 그 영역을 그대로 뒤집어서 비교하기엔 시간이 오래 걸리는 반면 양쪽을 비교하는 것은 조금만 틀려도 바로 조회를 끝내버릴 수 있기 때문이다.

또한 PalindromeLine() 함수를 마쳐 max_l을 반환하면, 이를 함수 외부의 max_l과 비교하여 더 크다면 갱신한다. 이렇게 max_l가 커지면 그보다 작은 영역에 대해서는 조회할 필요가 없으므로 회문의 조회 길이를 의미하는 PalindromeLine() 함수의 s의 영역은 max_l부터 시작하게 되는 것이다. max_1+1부터 시작해도 될 것 같지만 안전상 인덱스 하나를 줄였다.

어려웠던 문제였다. 동기들도 상당히 어려워하는 문제였다. 동기들의 풀이에 의하면 회문의 길이를 100부터 줄여오다가 회문을 발견하면 반복을 바로 끝낼 수 있기 때문에 더 효율적이라고 하였다. 나 역시 최대 회문 길이가 커짐에 따라 영역을 skip하기도 하는데, 초반에 회문의 길이를 점점 늘려가는 과정에서 시간을 더 소요하기 때문에 반대로 생각하는 연습이 필요하겠다고 느꼈다.

결과

PASS