[SWEA] 1215. 회문1/Python - D3

❓문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14QpAaAAwCFAYi

SW Expert Academy

성능 요약

재귀호출 ➡️ 메모리: 45,056 KB, 시간: 117 ms, 코드길이: 696 Bytes
반복문 ➡️ 메모리: 44,812 KB, 시간: 139 ms, 코드길이: 407 Bytes

✍🏻풀이

세로로 이어진 회문을 개수를 세기 위해 전치행렬로 바꾼다.
기본적으로 글자판의 크기는 8인데 l을 회문의 길이라고 하면 8-l+1 만큼 반복하여 글자만든다.
그 글자가 회문인 경우 1을 더한다.

💻코드

# 재귀호출
def palindromic(y, x, s):
    if len(s) == l:
        if s == "".join(s[::-1]):
            return 1
        else:
            return 0
 
    return palindromic(y, x + 1, s + board[y][x])
 
def t_palindromic(y, x, s):
    if len(s) == l:
        if s == "".join(s[::-1]):
            return 1
        else:
            return 0
 
    return t_palindromic(y, x + 1, s + t_board[y][x])
 
 
for tc in range(1, 11):
    l = int(input())
    board = [list(input()) for _ in range(8)]
    t_board = list(map(list, zip(*board)))
 
    res = 0
    for i in range(8):
        for j in range(8-l+1):
            res += palindromic(i, j, "")
            res += t_palindromic(i, j, "")
 
    print(f"#{tc} {res}")

# 반복문
for tc in range(1, 11):
    l = int(input())
    board = [list(input()) for _ in range(8)]
    t_board = list(map(list, zip(*board)))

    res = 0
    for i in range(8):
        for j in range(8-l+1):
            s = board[i][j:j+l]
            if s == s[::-1]:
                res += 1
            t_s = t_board[i][j:j+l]
            if t_s == t_s[::-1]:
                res += 1

    print(f"#{tc} {res}")

📍후기

처음에는 backtracking인가 생각했는데 방문 표시를 굳이 할 필요가 없어서 이걸 backtracking이라고 할 수 있을까 싶어서 visit은 만들지 않고 그냥 재귀로 생각하고 풀었다. 문제 댓글보니까 삼중반복문이라는 말도 있어서 삼중반복문으로도 풀어보았다. 시간은 재귀가 조금 덜 걸리는 것 같지만 메모리는 삼중반복문이 덜 차지하는 것 같다.