"기러기", "토마토", "스위스"와 같이 똑바로 읽어도 거꾸로 읽어도 똑같은 문장이나 낱말을 회문(回文, palindrome)이라 한다.
8x8 평면 글자판에서 제시된 길이를 가진 회문의 개수를 구하라.
위와 같은 글자판이 주어졌을 때, 길이가 5인 회문은 붉은색 테두리로 표시된 4개이므로 4를 반환하면 된다.
제한 사항 1. 각 칸의 들어가는 글자는 'A', 'B', 'C' 중 하나이다. 2. ABA도 회문이며, ABBA도 회문이다. A 또한 길이 1짜리 회문이다. 3. 가로 또는 세로로 이어진 회문의 개수만 센다. 4. 아래 그림에서 노란색 경로를 따라가면 길이 7짜리 회문이 되지만 직선이 아니기 때문에 인정되지 않는다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
평면 글자판을 순회하며 정해진 회문의 길이 안에서 회문 유무를 판별하는 구현 문제입니다. 행과 열을 순서로 탐색을 진행합니다.
slice 함수로 회문의 길이만큼 자르고 인덱스 증가폭을 -1로 설정하여 역순과 비교합니다. 이때 유의할 점은 반복할 행이나 열의 범위를 회문의 길이가 넘어서지 않도록 조절해야 합니다.
그리고 열을 탐색할 경우, Python의 리스트 슬라이싱 방식이 행 기준임을 고려해야 합니다. 따라서 별도의 리스트를 생성하고 역순과 비교를 진행합니다.
리스트 특성에 대한 이해와 응용력이 필요한 문제였고, 가로와 세로만 비교하면 간단히 해결할 수 있었습니다.
💡 내가 해결한 방식은?
word_length = int(input())
# 8 x 8 글자판
word_map = [list(map(str, list(input()))) for _ in range(8)]
count = 0
# 가로 탐색
for i in range(8):
for j in range(8 - word_length + 1):
if word_map[i][j:j + word_length] == word_map[i][j:j + word_length][:: - 1]:
count += 1
# 세로 탐색
for i in range(8):
for j in range(8 - word_length + 1):
if [word_map[k][i] for k in range(j, j + word_length)] == [word_map[k][i] for k in range(j, j + word_length)][:: -1]:
count += 1
print(count)
"기러기" 또는 "level" 과 같이 거꾸로 읽어도 제대로 읽은 것과 같은 문장이나 낱말을 회문(回文, palindrome)이라 한다.
주어진 100x100 평면 글자판에서 가로, 세로를 모두 보아 가장 긴 회문의 길이를 구하는 문제이다.
위와 같은 글자 판이 주어졌을 때, 길이가 가장 긴 회문은 붉은색 테두리로 표시된 7칸짜리 회문이다. 예시의 경우 설명을 위해 글자판의 크기가 100 x 100이 아닌 8 x 8으로 주어졌음에 주의한다.
제한 사항 1. 각 칸의 들어가는 글자는 c언어 char type으로 주어지며 'A', 'B', 'C' 중 하나이다. 2.글자 판은 무조건 정사각형으로 주어진다. 3. ABA도 회문이며, ABBA도 회문이다. A또한 길이 1짜리 회문이다. 4. 가로, 세로 각각에 대해서 직선으로만 판단한다. 즉, 아래 예에서 노란색 경로를 따라가면 길이 7짜리 회문이 되지만 직선이 아니기 때문에 인정되지 않는다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
글자 판 위에서 회문의 길이를 1부터 100까지 정하고 회문을 탐색하여 최대 길이를 구하는 문제입니다.
구현 과정에서 핵심은 회문의 길이가 100을 넘어가지 않도록 반복 순회하는 것입니다.
해당 길이에서 회문의 역순과 비교하여 회문 판별 이후 최댓 값을 구할 수 있었습니다.
💡 내가 해결한 방식은?
word_map = [list(map(str, list(input()))) for _ in range(100)]
max_length = float('-inf')
# 각 칸에 들어가는 언어 'A', 'B', 'C' 중 하나
# 반복 최소화를 위해 가장 긴 길이부터 역순으로 탐색
# 가로 탐색
for i in range(100):
for j in range(100):
for length in range(100, 0, -1):
if j + length <= 100:
if word_map[i][j : j + length] == word_map[i][j : j + length][::-1]:
max_length = max(max_length, length)
# 세로 탐색
for i in range(100):
for j in range(100):
for length in range(100, 0, -1):
if j + length <= 100:
if [word_map[k][i] for k in range(j, j+length)] == [word_map[k][i] for k in range(j, j+length)][::-1]:
max_length = max(max_length, length)
print(max_length)
