문제 : 회문2
"기러기" 또는 "level" 과 같이 거꾸로 읽어도 제대로 읽은 것과 같은 문장이나 낱말을 회문(回文, palindrome)이라 한다.
주어진 100x100 평면 글자판에서 가로, 세로를 모두 보아 가장 긴 회문의 길이를 구하는 문제이다.
위와 같은 글자 판이 주어졌을 때, 길이가 가장 긴 회문은 붉은색 테두리로 표시된 7칸짜리 회문이다.
예시의 경우 설명을 위해 글자판의 크기가 100 x 100이 아닌 8 x 8으로 주어졌음에 주의한다.
[제약사항]
각 칸의 들어가는 글자는 c언어 char type으로 주어지며 'A', 'B', 'C' 중 하나이다.
글자 판은 무조건 정사각형으로 주어진다.
ABA도 회문이며, ABBA도 회문이다. A또한 길이 1짜리 회문이다.
가로, 세로 각각에 대해서 직선으로만 판단한다. 즉, 아래 예에서 노란색 경로를 따라가면 길이 7짜리 회문이 되지만 직선이 아니기 때문에 인정되지 않는다.
[입력]
각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.
총 10개의 테스트케이스가 주어진다.
[출력]
#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 찾은 회문의 길이를 출력한다.
import sys
sys.stdin = open("input.txt", "rt")
def palindrome_row(data): # 100x100 가로 확인
cnt = 0
for length in range(100, 0, -1): # 100부터 1까지 줄여나가면서 최대 찾기
for i in range(100):
for j in range(100):
if j + length > 100: # 범위 벗어날 시 끝
break
e = j + length -1 # 마지막 인덱스
for k in range(j,j+length):
if data[i][k] != data[i][e]: # 회문이 아닐 시
break
e -= 1 # 통과할 때마다 끝 인덱스는 줄여나가야지
else: # 반복문 모두 돈 경우 : 회문이 맞아
cnt = length
return cnt # length는 100에서 줄여나가고 있기 때문에 바로 리턴하면 돼
def palindrom_col(data): # 100x100 세로 확인
cnt = 0
for length in range(100,0,-1):
for i in range(100):
for j in range(100):
if j + length > 100: # 범위 벗어날 시 끝
break
e = j + length -1 # 역시 마지막 인덱스로 설정
for k in range(j, j+length):
if data[k][i] != data[e][i]: # 회문이 아닌 경우
break
e -= 1
else:
cnt = length
return cnt
T = 10
for t in range(1,T+1):
n = int(input())
data = [list(map(str, input())) for _ in range(100)]
res = 0
cntA = palindrome_row(data)
cntB = palindrom_col(data)
res = max(cntA, cntB)
print(f"#{t} {res}")
코멘트
회문의 길이가 정해져 있지 않고, 가장 긴 회문의 길이를 구하는 것이므로 회문의 길이를 변수로 뒀어야 함. ( 하나하나 줄여가는 것은 생각하지 못했음. )
- 회문의 길이를 줄여가는 것이 더 좋았음 !!! ( 바로 탈출 가능 ! )
중요한게 가장 긴 회문을 찾아야 하기 때문에, 길이를 거꾸로 시작하면 반복횟수를 줄일 수 있지 않을까..? 생각할 수 있었어야 함.
문자열 그 자체를 구하는게 아닌, 개수를 구하면 되기 때문에 양 끝점을 계속 비교하면서 안쪽으로 들어가며 회문인지 판단하면 됐다 !!
- 가로 회문
- 구간 안에서 양 끝값이 같을 때만 확인
- 세로 회문
- 구간 안에서 양 끝 값이 같을 때만 안쪽 학인
