[Python] SW Expert Academy - 4861. 회문

SW Expert Academy 4861번 회문 문제는 NxN 크기의 글자판에서 길이가 M인 회문을 가로 또는 세로 방향으로 찾아 출력하는 문제이다. 회문이란 어느 방향에서 읽어도 같은 문자열이다. 문자열을 저장하고 조작하는 방법을 이해하고 이를 활용하는 문제로 난이도는 D2다.

 

SW Expert Academy 4861번 회문 문제 정보

알고리즘 분류

- palindrome 회문 판별

난이도

- D2

 

회문 문제 요약

• NxN 크기의 글자판에서 길이가 M인 회문을 가로 또는 세로 방향으로 찾아 회문을 출력하는 문제이다. 
• N의 범위는 10 이상 100 이하이다.
• 회문의 길이 M의 범위는 5~N이다.
• 회문은 1개만 존재하며, 가로 방향뿐만 아니라 세로 방향에서도 찾을 수 있다.

문제 풀이 과정

1. NXN 글자판에 입력받은 문자열들을 2차원 리스트 wordPan에 저장한다.
2. 먼저 가로 방향을 탐색한다.
3. 회문 길이의 절반만큼 반복하여 첫 번째 문자와 마지막 문자, 두 번째 문자와 마지막-1번째 문자... 순으로 비교하며 회문 검사를 수행한다.
4. 회문 검사를 성공하면 회문의 시작 위치를 저장하여 출력한다.
5. 회문 검사를 실패하면 세로 방향으로 회문 검사를 수행하여 회문을 찾는다.
6. 테스트 케이스 번호, 회문을 출력한다.

코드 및 설명

• wordPan [][] - NXN 글자판에 저장된 문자열들이 담긴 2차원 리스트
• row, column - 회문이 시작되는 행, 열의 위치
• cnt - 회문 비교 시 동일한 문자 수
• result - 글자판에서 찾은 회문을 저장하는 문자열

T = int(input())
for tc in range(T):
    N, M = map(int, input().split())
    wordPan = [[] for _ in range(N)]

    for i in range(N):
        wordPan[i] = list(input())

    row = column = 0
    cnt = 0
    result=''

    # 가로 방향 탐색
    for n in range(N):
        for i in range(N + 1 - M):

            # 회문 판별
            for idx in range(M // 2):
                if wordPan[n][idx + i] == wordPan[n][M - (idx + 1) + i]:
                    cnt += 1
                else:
                    cnt = 0
                    break
            # 회문 발견
            if cnt == M // 2:
                row, column = n, i
                break
        if cnt == M // 2:
            break

	# 가로 방향 탐색 성공
    if cnt == M // 2:
        for i in range(column, column + M):
            result += wordPan[row][i]
    else:
        # 세로 방향 탐색
        for n in range(N):
            for i in range(N + 1 - M):

                # 회문 판별
                for idx in range(M // 2):
                    if wordPan[idx + i][n] == wordPan[M - (idx + 1) + i][n]:
                        cnt += 1
                    else:
                        cnt = 0
                        break
                # 회문 발견
                if cnt == M // 2:
                    row, column = i, n
                    break
            if cnt == M // 2:
                break
                
        for i in range(row, row + M):
            result += wordPan[i][column]

    print("#{0} {1}".format(tc + 1, result))

---

SW Expert Academy 4861번 회문 문제는 문자열 활용 문제이며 파이썬을 사용하였다. 난이도는 D2인데, 단순히 palindrome 회문 판별 알고리즘이 아니라 활용 수준의 문제라서 생각을 조금 오래 하고 풀었다. 실력이 조금 더 향상된다면 리팩터링을 시도해봐야겠다.