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

2024년 5월 10일

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

SW Expert Academy

 

---

 

비슷한 문제

 

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

SW Expert Academy

 

 

풀이 : https://ymg5218.tistory.com/82

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

 

---

 

문제 접근

 

100 X 100 사이즈의 글자판에서 가장 긴 회문의 길이를 찾는 문제이다.

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

 

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

 

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

 

시간 제한이 파이썬 기준 테스트케이스 10개에 30초이며, 글자판의 크기가 100 X 100 이므로 브루트포스 방식을 채택하기 전 시간복잡도에 대해 고민해볼 필요가 있다고 생각했다.

 

한 행에 대해 모든 경우의 수를 판단해본다 생각했을 때,

1. 첫 번째 문자를 회문의 시작 문자로 가정하며 회문의 길이를 1씩 증가시켜 100까지 증가시킨다면, 총 100번 탐색해야 할 것이다.

2. 두 번째 문자를 회문의 시작 문자로 가정하여 회문의 길이를 1씩 증가시켜 99까지 증가시킨다면(2번째 문자부터 회문이 시작된다면 최대 회문의 길이는 100 - 1 = 99이다), 총 99번 탐색해야 할 것이다.

3. 마지막 문자를 회문의 시작 문자로 가정한다면 최대 회문의 길이는 1이며 총 1번 탐색해야 할 것이다.

 

 

1 ~ 3번의 과정을 토대로, 한 행에 존재하는 회문을 모두 탐색해 보았을 때 탐색 횟수는 다음과 같다.

 

100 + 99 + 98 + ... + 2 + 1 = (100 + 101) / 2

 

이는 시간복잡도 O(N^2) 라고 볼 수 있다.

 

이제 모든 행을 탐색해보자. 행은 N = 100개이므로 N^2 X N = N^3, 즉 O(N^3)이라고 볼 수 있다.

 

모든 행 뿐 아닌, 모든 열 또한 탐색해야하기 때문에 N^3 X 2 = 2*N^3, 즉 O(N^3)이다.

 

최종적으로 O(N^3)의 시간복잡도 로직을 구성하였을 때, N은 100이기 때문에 10개의 테스트케이스를 30초 내에 수행하는 시간적 여유를 토대로 브루트포스 방식을 채택해도 문제가 없어 보이기에 해당 방식을 그대로 가져가기로 하였다.

 

추가로 모든 행과 열을 탐색할 때, 만약 길이가 5인 회문이 발견되었다면 현재까지 발견한 회문의 최대 길이를 5로 지정해둔 뒤, 회문이 5보다 더 긴 경우가 존재하는지 계속 확인을 하는 방식으로 최대한 코드의 효율성을 높히기로 결정하였다.

 

(현재까지 회문의 길이가 최대 5임을 알아낸 상태에서, 이후엔 굳이 회문의 길이가 1~4인 경우는 알아낼 필요가 없기 때문이다.)

---

 

 

 

 

그렇다면 특정 문자열이 회문인지 어떻게 확인할 수 있는가?

 

 

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

 

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

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

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

 

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

 

 

 

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

 

 

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

 

 

---

 

순서도

 

1. 100 X 100 사이즈의 글자판 board를 2차원 배열 형태로 입력받는다.

2. 회문의 최대 길이를 담을 length를 선언하고 1로 초기화한다. (최소 회문 길이는 1이기 때문)

3. board의 각 행과 열을 모두 탐색하며 각 행과 열에 더 긴 회문이 존재하는지 탐색을 진행한다.
3-1. 길이가 k인 회문이 가장 긴 회문이라면, 그 다음 탐색부터는 k+1 인 회문이 존재하는지 완전탐색을 진행한다.

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

 

---

 

 

주의할 점

 

배열 슬라이싱이 익숙하고 회문의 특성을 이해해야 하며, 탐색 범위에 대한 조건문을 꼼꼼히 작성해야 자잘한 오류를 피할 수 있다.

 

---

 

전체 코드

 

'''
시간복잡도
각 행 완전 탐색 -> 100 + 99 + 98 + ... + 2 + 1 ~= 100^2
모든 행 완전 탐색 -> 100^2 x 100 = 100^3
모든 열 완전 탐색 -> 100^3
모든 테이블 완전 탐색 -> 2 x 100^3

O(N^3)이지만 N이 100이므로 가능하다 판단
'''

def isValid(arr):
    start = 0
    end = len(arr) - 1
    
    while start <= end:
        if arr[start] != arr[end]:
            return False
        start += 1
        end -= 1
    return True


def solution():
    # 최소 길이 : 1
    length = 1

    # 행 탐색
    for row in range(L):
        now_maxLen = length
        for col in range(L - length):
            for search_len in range(length + 1, L - col + 1):
                if board[row][col] == board[row][col + search_len - 1]:
                    temp = board[row][col: col + search_len]
                    if isValid(temp):
                        now_maxLen = search_len
            length = max(length, now_maxLen)
        # length가 최대 값이라면 함수 종료
        if length == L:
            return length

    # 열 탐색
    for col in range(L):
        now_maxLen = length
        for row in range(L - length):
            for search_len in range(length + 1, L - row + 1):
                if board[row][col] == board[row + search_len - 1][col]:
                    temp = []
                    for _row in range(row, search_len + row):
                        temp.append(board[_row][col])
                    if isValid(temp):
                        now_maxLen = search_len
            length = max(length, now_maxLen)
        if length == L:
            return length
    
    return length

T = 10

for _ in range(T):
    test_case = int(input())
    L = 100
    board = []
    for _ in range(L):
        board.append(input())
    
    
    print(f'#{test_case} {solution()}')

---

 

풀이 후기

 

브루트포스 방식이 가능한지 시간복잡도에 대해 고민해보고 과감히 결정을 내릴 수 있어 어렵지 않게 풀 수 있었다.