코딩테스트/SWExpertAcademy

회문1 Python(SW Expert Academy)

멍토 2020. 3. 15.

난이도 : D3

문제번호 : 1215

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14QpAaAAwCFAYi&categoryId=AV14QpAaAAwCFAYi&categoryType=CODE

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com


목차

1. 문제 설명

2. 문제 해석

3. 소스 코드


1. 문제 설명

"기러기" 또는 "level" 과 같이 거꾸로 읽어도 앞에서부터 읽은 것과 같은 문장이나 낱말을 회문(回文, palindrome)이라 한다.

주어진 8x8 평면 글자판에서 가로, 세로를 모두 보아 제시된 길이를 가진 회문의 총 개수를 구하는 문제이다.

글자판이 주어졌을 때, 길이가 5인 회문은 붉은색 테두리로 표시된 4개가 있으며 따라서 4를 반환하면 된다.

제약사항

각 칸의 들어가는 글자는 c언어 char type으로 주어지며 'A', 'B', 'C' 중 하나이다.

글자 판은 무조건 정사각형으로 주어진다.

ABA도 회문이며, ABBA도 회문이다. A또한 길이 1짜리 회문이다.

가로, 세로 각각에 대해서 직선으로만 판단한다.

즉, 아래 예에서 노란색 경로를 따라가면 길이 7짜리 회문이 되지만 직선이 아니기 때문에 인정되지 않는다.

입력

각 테스트 케이스의 첫 번째 줄에는 찾아야 하는 회문의 길이가 주어지며, 다음 줄에 테스트 케이스가 주어진다.

총 10개의 테스트 케이스가 주어진다.

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 찾은 회문의 개수를 출력한다.

예시

입력 출력
4
CBBCBAAB
CCCBABCB
CAAAACAB
BACCCCAC
AABCBBAC
ACAACABC
BCCBAABC
ABBBCCAA
4
BCBBCACA
BCAAACAC
ABACBCCB
AACBCBCA
ACACBAAA
ACCACCCB
AACAAABA
CACCABCB
...
#1 12
#2 10
...

 

2. 문제풀이

주어진 길이만큼의 회문이 몇개있는지를 구하는 문제였다.

가로 세로를 탐색하기 힘들어서

세로를 가로로 바꾸어 2개의 배열을 동시에 탐색하는 방식으로 풀었다.

회문을 체크하는 함수를 하나만들고

슬라이싱을 이용하여 현재 위치에서 + 구해야하는 길이만큼을 회문함수로 돌려

True라면 카운팅을 하도록 만들었다.

 


3. 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# D3 1215 회문1
def check(a):
    l = len(a)
    for i in range(l//2):
        if a[i] != a[l-i-1]:
            return False
    return True
 
= 10
for t in range(1, T+1):
    length = int(input())
    map_list = []
    map_list2 = []
    N = 8
    for i in range(N):
        map_list.append(input())
    for i in range(N):
        str_temp = ''
        for k in range(N):
            str_temp += map_list[k][i]
        map_list2.append(str_temp)
    result = 0
    for i in range(N):
        for j in range(N-length+1):
            if check(map_list[i][j:j+length]):
                result += 1
            if check(map_list2[i][j:j+length]):
                result += 1
            
    print("#{} {}".format(t, result))

댓글

💲 광고입니다.