서론
오늘도 SW Expert Academy에서 D3 난이도의 문제를 풀었습니다. 성공률이 높아 쉬울 것 같았는데 크게 어렵지 않았습니다.
문제 분석
이 문제는 8x8 크기의 글자판이 주어지고, 가로 또는 세로 방향으로 주어진 길이의 회문의 개수를 찾는 것입니다.
제약 사항은 다음과 같습니다:
•
각 칸에는 'A', 'B', 'C' 중 하나의 문자만 들어갑니다.
•
ABA나 ABBA 모두 회문으로 인정됩니다.
•
A와 같은 길이 1의 문자열도 회문입니다.
•
오로지 가로나 세로 방향으로 연결된 회문만 카운트합니다.
입력으로는 10개의 테스트 케이스가 주어지며, 각 케이스마다 찾아야 할 회문의 길이와 8x8 글자판이 주어집니다.
계획 수립
글자판의 크기가 8x8로 고정되어 있고 그리 크지 않기 때문에, 단순히 이중 for문을 사용해 모든 가능한 경우를 탐색해도 충분할 것 같습니다. 가로와 세로 방향을 모두 확인하면서 주어진 길이의 회문이 존재하는지 체크하고 카운트를 세면 될 것 같습니다.
코드 작성
import sys
sys.stdin = open("input.txt", "r")
T = 10
for test_case in range(1, T + 1):
N = int(input())
Map = [[x for x in input()] for _ in range(8)]
count = 0
for i in range(8):
for j in range(8-N+1):
flags = [True, True]
for k in range(N):
if flags[0] and Map[i][j+k] != Map[i][j+N-k-1]:
flags[0] = False
if flags[1] and Map[j+k][i] != Map[j+N-k-1][i]:
flags[1] = False
if flags[0]:
count += 1
if flags[1]:
count += 1
print("#%d %d" % (test_case, count))
Python
복사
행렬 크기가 고정되어 있어서 구현이 좀 수월했습니다. 모든 행과 열을 이중 for문으로 돌면서 가로와 세로 방향의 substring을 추출하여 회문 여부를 판별했습니다.
문제 해결 및 보완
제출한 코드가 모든 테스트 케이스를 통과했습니다. 메모리나 실행시간 측면에서도 낭비되는 부분은 없어보입니다.
회고
오늘은 쉬운 문제를 골라서 금방 풀 수 있었네요. 그래도 8x8이 아니라 NxN 행렬로 일반화한다면 조금 더 생각할 거리가 있었을 것 같습니다. 내일은 조금 더 난이도 있는 문제에 도전해봐야겠습니다.
