[Python 파이썬] SWEA 1215번 - [S/W 문제해결 기본] 3일차 - 회문1

2024년 5월 8일

문제 링크 : SWEA 1215번 - [S/W 문제해결 기본] 3일차 - 회문1

SW Expert Academy

---

 

 

문제 접근

 

8 X 8 사이즈의 글자판에서 회문을 찾는 문제이다.

회문이란, 문자열 뒤집었을 때 원래 문자열과 같은 문자열을 의미하며 예시로는 '기러기', '역삼역', 'ABCBA' 등이 있다.

 

또한 한 글자 또한 뒤집으면 같은 글자가 되기에 'A', 'Z' 같은 한 글자 또한 회문으로 간주한다.

 

입력 값으로 찾아야 하는 회문의 길이와 글자판이 주어졌을 때, 길이에 부합하는 회문이 총 몇 개 인지 찾는 문제이다.

단, 회문은 가로 혹은 세로로 이어져있어야 유효하다.(대각선 불가능)

 

시간 제한이 파이썬 기준 테스트케이스 10개에 30초이며, 글자판의 크기 또한 8 X 8 사이즈이므로 브루트포스 방식을 채택해도 무방하다고 판단했다.

 

모든 행을 순서대로 탐색하며 각 행에 회문이 있는지 탐색할 것이며, 무작정 특정 길이의 모든 문자열을 조합하여 확인하는 것보다, 다음과 같이 회문의 특성을 이용하여 가지치기를 통해 시간복잡도를 조금이나마 줄여보기로 했다.

 

---

 

다음과 같은 문자열이 회문인지 어떻게 확인할 수 있는가?

 

 

길이가 5인 회문을 찾는다고 가정하겠다.

 

일단 회문은 뒤집어도 같기에,

해당 문자열이 만약 회문이라면 현재 탐색중인 문자열의 시작점 arr[0]과 arr[4]의 요소가 같아야 할 것이다.

만약 다르다면 나머지 요소들을 탐색할 필요 조차 없어지기에 불필요한 연산 생략이 가능하다.

 

만약 문자열의 시작점과 끝점이 같다면, 양 옆으로 포인트를 한 칸씩 땡겨 탐색을 진행하면 된다.

 

 

 

회문이 맞는지 확인하는 로직이 끝날때까지 유효함을 유지했다면, True를 반환하며 해당 문자열이 회문임을 알 수 있다.

 

 

만약 로직 중간에 회문이 아님을 결정났다면, 추가 연산을 생략하고 False를 반환하며 해당 문자열이 회문이 아님을 도출해낸다.

 

또한, 이 문제는 정해진 길이의 회문을 알아내는 것이기에 다음과 같은 방식으로도 추가 연산을 막을 수 있다.

 

 

---

 

순서도

 

1. 찾고자 하는 회문의 길이 length를 입력받고, 8 X 8 사이즈의 글자판 board를 2차원 배열 형태로 입력받는다.

2. 회문의 개수를 담을 cnt를 선언한다.

3. board의 각 행과 열을 모두 탐색하며 각 행과 열에 회문이 존재하는지 판별한다.
3-1. 각 행과 열의 현재 탐색하는 인덱스 값이, 해당 값으로 시작하는 length 길이의 문자열 마지막 값과 같다면 유효성 검사를 수행한다.
3-2. 유효성 검사 결과가 True라면 cnt를 1 증가시킨다.

4. 로직이 종료되면 cnt를 출력한다.

 

---

 

입력 예제

 

4
CBBCBAAB
CCCBABCB
CAAAACAB
BACCCCAC
AABCBBAC
ACAACABC
BCCBAABC
ABBBCCAA
4
BCBBCACA
BCAAACAC
ABACBCCB
AACBCBCA
ACACBAAA
ACCACCCB
AACAAABA
CACCABCB
...

 

---

 

출력 예제

 

#1 12
#2 10
...

 

---

 

 

주의할 점

 

배열 슬라이싱이 익숙하고 회문의 특성을 이해했다면 조건문 작성에 크게 어려움이 없었을 것이라 생각한다.

---

 

전체 코드

 

def isValid(arr):
    i = 1
    while i < length // 2:
        if arr[i] != arr[length - i - 1]:
            return False
        i += 1
    return True


def solution():
    cnt = 0
    # 각 행 탐색
    for row in range(8):
        for col in range(8 - length + 1):
            if board[row][col] == board[row][col + length - 1]:
                temp = board[row][col : col + length]
                if isValid(temp):
                    cnt += 1

    # 각 열 탐색
    for col in range(8):
        for row in range(8 - length + 1):
            if board[row][col] == board[row + length - 1][col]:
                temp = []
                for i in range(row, row + length):
                    temp.append(board[i][col])
                if isValid(temp):
                    cnt += 1

    return cnt

T = 10

for test_case in range(1, T + 1):
    length = int(input())
    board = []
    for _ in range(8):
        board.append(list(input()))

    print(f'#{test_case} {solution()}')

---

 

풀이 후기

 

브루트포스 방식으로 풀었고 나름 가지치기 로직도 추가하였으나, 더 효율적인 코드가 분명 있을 것이라 생각된다.