[인프런] 격자판 회문수

---

문제설명

1부터 9까지의 자연수로 채워진 7 by 7 격자판이 주어지면 격자판 위에서 가로방향 또는 세로방향으로 길이 5자리 회문수가 몇 개 있는지 구하는 프로그램을 작성해라. 회문수란 121과 같이 앞에서부터 읽으나 뒤에서부터 읽으나 같은 수를 말한다.

 

 

단, 빨간색 처럼 구부러진 경우(87178)는 회문수로 간주하지 않는다.

입력조건

• 1부터 9까지의 자연수로 채워진 7 by 7 격자판이 주어진다.

출력조건

• 5자리 회문수의 개수를 출력한다.

사고과정

• 우선 데이터 범위가 7로 정해져있기도 하고 5자리이기 때문에 객 행, 열 방향으로 1칸씩 최대 2번 이동할 수 있다. 행에서는 구현하기 쉬웠지만 열 방향으로는 구현하는 데 고민을 했다. 리스트는 넘파이와 달리 열 방향으로 슬라이싱이 불가능하기 때문이다. 그래서 열 방향으로 돌 때 따로 구현하도록 했다. 그리고 회문수를 체크하는 방법은 문자열을 뒤집는 슬라이싱 기법인 [::-1]를 사용해도 되었지만 저번에 배운 loop로 구현해보았다. 
• 강의 풀이를 보니 행과 열 방향을 동시 탐색을 수행할 수 있었다! 매우 인상적이었다..
• 우선 행과 열 방향으로 어차피 2번씩 탐색을 수행하기 때문에 행 방향을 탐색할 때 열 방향도 동시탐색을 수행했다. 텍스트로 말하기는 너무 못알아들을 것 같아서 하단의 '강의 풀이' 소스코드를 꼭 보자!
• 내 풀이가 강의 풀이보다 시간복잡도 면에서 안좋은 점이 아쉬웠다..

풀이

- 나의 풀이

def check(tmp):
    n = len(tmp)
    for i in range(n//2):
        if tmp[i] != tmp[-1-i]:
            return False
    return True
    
arr = [list(map(int, input().split())) for _ in range(7)]
count = 0
# 행 방향 탐색
for i in range(7):
    for j in range((7 % 5)+1):
        tmp = arr[i][j:j+5]
        if check(tmp):
            count += 1
# 열 방향 탐색
for j in range(7):
    for k in range(3):
        tmp = []
        for i in range(0, 5):
            tmp.append(arr[i+k][j])
        if check(tmp):
            count += 1
print(count)

- 강의 풀이

# 강의 Solution -> 회문수는 슬라이싱 reverse 기법 적용, loop안에서 행, 열 방향 동시 탐색 가능함..
board = [list(map(int, input().split())) for _ in range(7)]
cnt = 0
# 행 방향 탐색
for i in range(3):
    for j in range(7):
        tmp = board[j][i:i+5]
        if tmp == tmp[::-1]:
            cnt += 1
        # 열 방향 탐색 -> 행 방향 탐색 시 i, j 가 소속된 루프가 열 방향으로 1칸 씩 shift시키면서 자동 탐색 수행
        # 아래 loop는 회문수 체크용
        for k in range(2):
            if board[i+k][j] != board[i+5-k-1][j]:
                break
        else:
            cnt += 1
print(cnt)