[SWEA] D3. 회문2

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV14Rq5aABUCFAYi&categoryId=AV14Rq5aABUCFAYi&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=PYTHON&select-1=3&pageSize=10&pageIndex=2

SW Expert Academy

 

 

1. 해결방법

나름 좋은 문제였다. 완전탐색으로 해결하였고, 디버깅 포함 1시간 정도 걸렸다.

회문을 탐색할 때, row와 col로 나누어서 탐색을 하였다. 
가로에선느 최대 회문의 가능 개수를 구하는 것이기 때문에 2중 for문에서 회문의 길이를 측정해주는 for문을 더 추가하여 1부터 100까지의 회문의 길이를 구할 수 있도록 구현하였다.

세로같은 경우는 로직은 똑같지만 리스트 슬라이스 적용 위치가 다르기 때문에 temp라는 문자열 변수로 각 열의 문자를 더해서 if문으로 조건을 추가하였다.

col에서 k <= answer 분기문을 추가해서 나름의 가지치기를 적용함.

 

 

 

2. 정답코드

T = 10
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N = int(input())
    maps = [list(map(str, input().strip())) for _ in range(100)]

    # row
    answer = 0
    for i in range(100):
        for k in range(1, 100):
            for j in range(100 - k + 1):
                if maps[i][j:j + k] == maps[i][j:j + k][::-1]:
                    answer = max(answer, k)
                    break

    # col
    for j in range(100):
        for k in range(1, 100):
            if k <= answer:
                continue
            for i in range(100 - k + 1):
                temp = ''
                for s in range(i, i + k):
                    temp += maps[s][j]
                if temp == temp[::-1]:
                    answer = max(answer, k)
                    break

    print(f"#{test_case} {answer}")