[SWEA|파이썬] 1216. [S/W 문제해결 기본] 3일차 - 회문2 (D3)

문제

https://tinyurl.com/2qtn6fuh

SW Expert Academy

 

 

🐍파이썬

for test_case in range(1, 11):
    int(input())
    arr = []
    max_len = 0
    for _ in range(100):
        arr.append(list(input()))
    for i in range(100):
        b = ''	#세로문자열 초기화
        #가로 문자열 확인
        for j in range(100):
            for k in range(100-j+1):
                #회문 길이(k)만큼의 문자열과 그 역순 문자열을 비교
                if arr[i][j:j+k] == arr[i][j:j+k][::-1]:	
                    max_len = max(max_len, k)	#max_len 갱신
            b += arr[j][i]	#세로문자열에 문자추가
        #세로 문자열 확인
        for m in range(100):
            for n in range(100-m+1):
                if b[m:m+n] == b[m:m+n][::-1]:
                    max_len = max(max_len, n)
    print("#{} {}".format(test_case, max_len))

테스트케이스 5번 fail이 떠서 시간을 많이 잡아먹었다.

알고 보니 문자열 범위를 계속 for k in range(100-j)으로 지정해서 회문길이를 99개까지밖에 확인을 안 해서 생긴 오류...

👉 for k in range(100-j+1) 으로 바꾸었더니 pass 뜸

범위 확인 잘 하자...

 

 

다른 풀이 방법

def get_solution2(arr, m):	#회문 확인 함수
    for word in arr:  # 1 ~ 100
        for s in range(100 - m + 1):
            for k in range(m//2):
                if word[s+k] != word[s + m -1 -k]:
                    break
            else:
                return m
    return 0
 
 
T = 10
for _ in range(1, T+1):
    t = int(input())
    a = [input() for _ in range(100)]
    b = [''.join(x) for x in zip(*a)]	#행/렬 위치 변경
 
    #가로 회문 확인
    maxLength = 1
    for m in range(2, 101):
        if m > maxLength + 2: break
        if maxLength < get_solution2(a, m):
            maxLength = m
 
    #가로 회문 확인
    m = maxLength + 1
    for m in range(maxLength+1, 101):
        if m > maxLength + 2: break
        if maxLength < get_solution2(b, m):
            maxLength = m
 
    print('#%d %s' % (t, maxLength))