[탐색 및 시뮬레이션] 파이썬 알고리즘 문제 2-11 "격자판 회문수"

격자판 회문수

 

[시간복잡도]

O(N³) = for문을 세 번 이용해서 O(N³)의 시간복잡도가 나온다.

[공간복잡도]

O(N²) = 격자판 자체가 O(N²)의 공간복잡도를 가진다.

 

Problem

 

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

 

 

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

 

▣ 입력설명

 

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

 

▣ 출력설명

 

5자리 회문수의 개수를 출력합니다.

 

▣ 입력예제

2 4 1 5 3 2 6

3 5 1 8 7 1 7

8 3 2 7 1 3 8

6 1 2 3 2 1 1

1 3 1 3 5 3 2

1 1 2 5 6 5 2

1 2 2 2 2 1 5

 

▣ 출력예제

 

3

 

 

 

💯 Solution ①

 

import sys
sys.stdin=open("input.txt","rt")
 
a=[list(map(int,input().split())) for _ in range(7)]
 
cnt=0
for i in range(3):
    for j in range(7):
        word=a[j][i:i+5]
        #제일 앞과 제일 뒤 인덱스를 비교
        if word==word[::-1]:
            # 둘이 똑같다면 cnt+1
            cnt+=1
        for k in range(2):
            if a[i+k][j]!=a[i+4-k][j]:
                break
        else:
            cnt+=1
 
print(cnt)

- 이중 for문으로 접근한다.

- 첫번째 for문은 i값으로 0,1,2만 들어갈 수 있기 때문에 (가로, 세로로 4칸을 비교해야하기때문에)

- j는 7개의 배열은 반복해야해서 range(7)이다.

 

- word에 5개의 길이의 배열을 슬라이싱해서 가져온다.

=> word=a[j][i:i+5]

 

- 만약 word와 거꾸로한 word[::-1]가 같다면, 해당 배열은 회문수인 것이므로 cnt+=1을 한다.

=> if wrod==word[::-1]: cnt+=1 

 

- 이제 가로는 5개씩 다 검사를 했지만, 세로는 아직 진행을 못했기 때문에, 세로줄을 5개씩 비교한다.

=> 

 

for k in range(2):

if a[i+k][j] != a[i+4-k][j]:

     break

else:

     cnt+=1

 

해당 for문을 통해서 k 는 0, 1을 반복하고, i는 for문을 돌기 전이기 때문에 i=0, j=0~6이 들어간다.

조건문을 통해서 a[0+0][0] 와 a[0+4-0][0] 을 비교한다. 

따라서, a[0][0] 와 a[4][0]을 비교하는 조건문을 통해서, 만약에 다르다면, 해당 for문은 그만 돌고 다음으로 넘어간다. (break를 통해서)

 

(j=0)

 

a[0][0], a[4][0]

a[1][0], a[3][0]

 

a[1][0], a[5][0]

a[2][0], a[4][0]

 

a[2][0], a[6][0]

a[3][0], a[5][0]

 

-----------------

(j=1)

 

a[0][1], a[4][1]

a[1][1], a[3][1]

 

a[1][1], a[5][1]

a[2][1], a[4][1]

 

a[2][1], a[6][1]

a[3][1], a[5][1]

 

-----------------

 

(j=2)

 

a[0][2], a[4][2]

a[1][2], a[3][2]

 

a[1][2], a[5][2]

a[2][2], a[4][2]

 

a[2][2], a[6][2]

a[3][2], a[5][2]

 

....

 

---------------

 

(j=7)

 

a[0][7], a[4][7]

a[1][7], a[3][7]

 

a[1][7], a[5][7]

a[2][7], a[4][7]

 

a[2][7], a[6][7]

a[3][7], a[5][7]

 

 

이를 통해서 세로열을 모두 반복하면서 체크한다.

 

만약, break문에 걸리지않고 for k in range(2)를 완벽하게 돈다면 cnt+=1을 한다.

 

마지막으로 cnt를 출력하면 출력양식대로 값이 나온다.

 

 

💯 Solution ②

: 튜터님의 코드

#Tutor's Code
import sys
sys.stdin=open("input.txt", "r")
board=[list(map(int, input().split())) for _ in range(7)]
cnt=0
# i는 0,1,2 만 가능하다. 3이상이면 5개를 했을 때, 격자판 밖으로 벗어난다.
for i in range(3):
    for j in range(7):
        # j가 행 / i가 5개씩 분리하기
        tmp=board[j][i:i+5]
        # 거꾸로 만들어 내는 것
        # 가로(행)로 체크
        if tmp==tmp[::-1]:
            cnt+=1
        # 길이가 5개짜리는 0,1,2만 하면 됨
        # 세로(열)를 체크
        for k in range(2):
            #
            if board[i+k][j]!=board[i+5-k-1][j]:
                break
        #정상적으로 for문을 종료하면, else문을 탐
        else:
            cnt+=1
            
print(cnt)

 

📚 참고

 

⚙️저장소

github.com/JiHoon-JK/Algorithm/blob/main/inflearn/python/%EC%84%B9%EC%85%983-11.py

JiHoon-JK/Algorithm