팰린드롬 | 1216. [S/W 문제해결 기본] 3일차 - 회문2

문제

SW Expert Academy

 

 

 

앞으로 읽거나 뒤로 읽어도 같은 글자를 회문, 팰린드롬이라고 한다.

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

회문은 직선으로만 판단한다.

 

입력

• 총 10개의 테스트 케이스
• 첫 줄: 테스트 케이스 번호
• 다음 줄: 테스트 케이스

1
CCBBCBAABCCCBABCBCAAAACABBACCCCACAABCBBACACAACABCBCCB...
ACBAAAACCACCCBAACAAABACACCABCBCBABBBACBABCAACCBCCACBC...
CCCACCBCBACBACBCABAABABCCAAAACCCCCBBAABBCCBCCCABBACAC...
CABACBCBBCBABACABBBBBBABBCABCBCBCAABCBCCCBABACCCCABBA...
BCCBCCACCBCBCABBBCCABAACACCBCCCBCCACCBBCBCCCBBCCBACBC...
BBBBCBBAACABACCBCBCCABBBBCCAABCBBCACCBBCAAAABABABBABB...
ABBAACCCACBBABBABCCCABABCACABABACCCBACACABCBCCCBABCCC...
ABBBBAABCAACCBACBBAACACABCABACBAABCAABBCCCCCCACBCCCCA...
ACCACABABBACBBAACCBBACBBCCACCACCABCCBABABBBACBACBAABC...
BABACACCABCAACBAABCCACCACBCCAABBCBAABABAACAAAAAACCCBC...
...
2
...

 

출력

#{테스트 케이스 번호} {가장 긴 회문의 길이} 
#1 18
#2 17

 

 

풀이

 

팰린드롬 문제를 풀 때는 중심 확장 방식이 가장 많이 사용된다.

 

중심 확장 방식은 홀수 팰린드롬이라고 가정할 때는 하나의 문자를 중심으로,

짝수 팰린드롬이라고 가정할 때는 두 개의 문자를 중심으로 잡고 좌우로 확장하는 방식이다.

 

물론 홀수 팰린드롬인지 짝수 팰린드롬인지는 미리 알 수 없으므로 두 방식 모두 검사해야 한다.

---

 

예를 들어 홀수 팰린드롬이라고 가정할 때 'CABAC'라는 문자열이 있다고 하자.

0번 인덱스의 'C'를 중심으로 잡는 것부터 시작하여 좌우를 확장하면서 가장 긴 팰린드롬을 찾는다.

0: 'C'에서 좌로 확장 불가하므로 팰린드롬의 길이는 1

1: 'A'에서 좌우로 확장했을 때 'C'와 'B'로 두 문자가 동일하지 않다.
    팰린드롬의 길이는 1

2: 'B'에서 좌우로 확장했을 때 'A'와 'A'로 동일.
    한 번 더 확장했을 때 'C'와 'C'로 동일.
    더 이상 좌우로 확장이 불가하다. 팰린드롬의 길이는 5

3: 'A'에서 좌우로 확장했을 때 'B'와 'C'로 두 문자가 동일하지 않다.
    팰린드롬의 길이는 1

4: 'C'에서 우로 확장이 불가하므로 팰린드롬의 길이는 1

 

위와 같이 중심 문자로부터

1) 좌우로 확장이 가능한지

2) 확장했을 때 두 문자가 같은지

확인하며 가장 긴 팰린드롬의 길이를 찾을 수 있다.

---

 

짝수 팰린드롬이라고 가정할 때 'ABBA'라는 문자열이 있다고 하자.

0번 인덱스의 'A'와 1번 인덱스의 'B'를 중심으로 잡고 두 문자를 비교하는 것부터 시작하며 좌우로 확장하여 가장 긴 팰린드롬을 찾는다.

0, 1: 0번 인덱스의 'A'와 1번 인덱스의 'B'가 같지 않다. 팰린드롬의 길이는 1
1, 2: 1번 인덱스의 'B'와 2번 인덱스의 'B'가 같다.
        좌우로 확장했을 때 0번 인덱스의 'A'와 3번 인덱스의 'A'가 같다.
        더 이상 좌우로 확장이 불가하다. 팰린드롬의 길이는 4
2, 3: 2번 인덱스의 'B'와 3번 인덱스의 'C'가 같지 않다. 팰린드롬의 길이는 1

 

위와 같이 두 중심 문자로부터

1) 두 중심 문자가 같은지

2) 좌우로 확장 가능한지

3) 확장했을 때 두 문자가 같은지

확인하며 가장 긴 팰린드롬의 길이를 찾을 수 있다.

 

---

 

 

def expand(left, right, s):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1

for _ in range(10):
    test_num = int(input().strip())
    test_case = [input().strip() for _ in range(100)]
    #세로 문자열 만들기
    test_case_cols = [''.join(test_case[r][c] for r in range(100)) for c in range(100)]         
    result = 1
    for text in test_case + test_case_cols:
        for j in range(100):
            expanded_result_1 = expand(j, j, text)
            expanded_result_2 = expand(j, j+1, text)
            result = max(expanded_result_1, expanded_result_2, result)
    print(f"#{test_num} {result}")

 

 

이 문제의 경우 세로 문자열이 팰린드롬인지도 확인해야 한다.

입력받은 100x100의 문자를 재구성하여 세로 문자열을 만들어주고, 해당 문자열을 검사하는 방식으로 진행한다.