SWEA 1216 파이썬 문제풀이(회문2)

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

 

---

 

이 문제는 SWEA1215와 유사한 문제이다.(https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14QpAaAAwCFAYi )

단, 차이점은 가장 길이가 긴 회문을 찾는것이고 이를 찾기위해서는 뽑은 카드 개수가 1~100개일 때 모두를 검사해야 한다는 것이다.

그런데, 1~100 개를 모두 검사하면 실행시간이 어마할 것이다. 따라서 실행 시간을 줄이기위해 100개를 뽑았을 때 부터 검사하여 만약 회문이 나온다면 바로 검사를 종료하는 것이다.

그렇게 가로를 우선적으로 구한 후 세로를 구하면 만약 세로를 구하다가 가로에서 구한 회문길이보다 짧다면 바로 검사를 종료해버리는 식으로 코드를 구현하였다.

 

# 가로 회문 검사
def checking_c():
    global count

    for K in range(100, 0, -1):  # 가장 큰 개수인 100개 부터 ~ 1개 까지 뽑아주며 검사
        for i in range(100):
            for j in range(100):
                if j + K > 100:  # 만약 K를 뽑을 수 없다면
                    break  # 반복문 탈출후 다음 행으로 넘어간다.
                e = j + K - 1  # 끝 인덱스를 설정
                for h in range(j, j + (K // 2)):  # 절반을 돌면서
                    if word[i][h] != word[i][e]:  # 양쪽에서 안으로 들어오면서 검사하는데 만약 다르다면
                        break  # 반복문탈출
                    e -= 1  # 끝쪽 인덱스를 -1씩 해준다.
                else:  # 반복문을 다돌았다면 회문이므로
                    count = K  # 그 길이를 설정 후
                    return  # 함수 탈출


# 세로 회문 검사
def checking_r():
    global count

    for K in range(100, 0, -1):  # 가장 큰 개수인 100개 부터 ~ 1개 까지 뽑아주며 검사
        if count >= K:  # 만약 가로에서 뽑은 회문 길이보다 이미 뽑을 K개가 더 작아졌다면 더이상 의미없으므로
            return  # 함수 리턴
        for i in range(100):
            if i + K > 100:  # 만약 K개를 뽑을 수 없다면
                break  # 반복문 탈출
            for j in range(100):
                e = i + K - 1  # 끝 인덱스 설정
                for h in range(i, i + (K // 2)):  # 절반을 나누어 양쪽 끝에서 안으로 들어면서 검사
                    if word[h][j] != word[e][j]:  # 만약 대칭을 기준으로 글자가 다르다면
                        break  # 반복문탈출
                    e -= 1  # 끝 인덱스를 -1씩 해준다.
                else:  # 반복문을 다돌았다면 회문이므로
                    count = K  # 그 개수를 K로 저장 후
                    return  # 탈출


for _ in range(1, 10 + 1):
    order = int(input())
    word = [list(map(str, input())) for _ in range(100)]

    count = 0
    # 가로 검사
    checking_c()

    # 세로 검사
    checking_r()

    print(f'#{order} {count}')