팰린드롬? ( 10942 번 )

10942번: 팰린드롬?

 

🧠 알고리즘

숫자 수열에서 주어진 구간이 팰린드롬(회문) 인지 판별하는 문제.
동적 계획법(DP)을 이용해 수열의 모든 구간에 대해 팰린드롬 여부를 미리 계산하고
질의마다 빠르게 정답을 출력.

 

🧾 코드

import sys

def _main(n, n_list):
    ''' 팰린드롬: 1, 팰린드롬 X: 0 '''
    answer = [[0] * n for _ in range(n)]

    ct = 0
    for lenth in range(1, n + 1):
        for start in range(n + 1 - lenth):
            end = start + lenth - 1

            if lenth == 1: # 자기 자신 이면 >> 팰린드롬
                answer[start][end] = 1
            elif (lenth == 2) and (n_list[start] == n_list[end]): # 길이가 2면 앞뒤 같으면 >> 팰린드롬
                answer[start][end] = 1
            elif (lenth >= 3) and (n_list[start] == n_list[end]) and (answer[start + 1][end - 1] == 1): # 길이가 3 이상 이면,, 양 끝과 가운데가 팰린드롬 이면 >> 팰린드롬
                answer[start][end] = 1
    
    return answer


n = int(sys.stdin.readline().rstrip())
n_list = tuple(map(int, sys.stdin.readline().rstrip().split()))
pd = _main(n, n_list)

case_count = int(sys.stdin.readline().rstrip())
for _ in range(case_count):
    start, end = map(int, sys.stdin.readline().rstrip().split())
    start, end = (start - 1), (end - 1)
    print(pd[start][end])

 

⏱️ 시간 복잡도

# 이중 for문 으로 모든 구간에 대해 팰린드롬 확인
for lenth in range(1, n + 1):
	for start in range(n + 1 - lenth):
    
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )