[백준] 10942 : 필린드롬?

비가츄·2024년 2월 21일

문제설명

N(1<=N<=2,000)개의 숫자(1<=X<=100,000)로 이루어진 배열(A)이 주어진다.
사용자로부터 시작번호 S와 끝번호 E를 받고, A에 대해 S번째부터 E번째까지의 배열이 팰린드롬인지를 확인한다.
팰린드롬일 경우 1을, 아닌 경우 0을 출력한다.
이때 입력은 M(1<=M<= 1,000,000)번 주어진다.

시간 제한

Java 8: 2.5 초
PyPy3: 1.5 초
Java 8 (OpenJDK): 2.5 초
Java 11: 2.5 초
PyPy2: 1.5 초
Kotlin (JVM): 2.5 초

접근

접근 1

일단 입력받을 때마다가 아닌, 모든 입력 경우의 수에 대해 계산을 미리 해보자는 생각으로 코드를 작성했다.

# 팰린드롬 골드4
import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
M = int(input())
C = [[False for x in range(N)] for y in range(N)]
answer = []

for s in range(N):
    C[s][s] = True
    for e in range(s+1, N):
        if A[s]!=A[e]:
            continue
        flag = True
        for i in range((e-s+1)//2):
            if A[s+i]!=A[e-i]:
                flag = False
                break
        if flag:
            C[s][e] = True

for m in range(M):
    S, E = map(int, input().split())
    if C[S-1][E-1]:
        answer.append("1")
    else:
        answer.append("0")

print("\n".join(answer))

이중 반복문을 통해 각 문자열의 시작점, 끝점에 따라서 팰린드롬 여부를 확인한다.
해당 코드는 당연히 시간초과가 났다.

접근 2(참고풀이)

30분 이상 생각해봤는데 아이디어가 떠오르지 않아서 결국 다른 사람의 풀이를 참고했다.
풀이는 다음과 같았다.

먼저 각 입력에 대한 팰린드롬 여부를 계산하여 배열에 넣는 아이디어는 동일하다.
배열을 구현하는 방법은 다음과 같다.

길이가 1인 배열은 무조건 팰린드롬이므로 C[x][x] = True로 설정한다.
길이가 2인 배열은 시작과 끝이 동일한 경우에만 True로 설정한다.
길이가 n(2<n)인 배열은 시작과 끝이 동일하며, 시작과 끝을 제외한 배열이 팰린드롬인 경우에만 True로 설정한다.

위의 조건을 각각 길이를 늘려가면서 배열을 채우면 되는 문제였다.
따라서 구현한 코드는 다음과 같다.

# 팰린드롬 골드4
import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
M = int(input())
C = [[False for x in range(N)] for y in range(N)]
answer = []

# 길이가 1인 배열은 무조건 팰린드롬
for i in range(N):
    C[i][i] = True

# 길이가 2인 배열은 시작과 끝이 동일하면 팰린드롬
for i in range(N-1):
    if A[i] == A[i+1]:
        C[i][i+1] = True

# 길이가 3이상인 배열은 
# 1) 시작과 끝이 동일하며,
# 2) 시작과 끝을 제외한 배열이 팰린드롬이면 팰린드롬
for len in range(2, N):
    for i in range(N-len):
        if A[i]==A[i+len] and C[i+1][i+len-1]:
            C[i][i+len] = True

for m in range(M):
    S, E = map(int, input().split())
    if C[S-1][E-1]:
        answer.append("1")
    else:
        answer.append("0")

print("\n".join(answer))

소스코드

최종적으로 제출한 코드는 다음과 같다.

# 팰린드롬 골드4
import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
M = int(input())
C = [[False for x in range(N)] for y in range(N)]
answer = []

# 길이가 1인 배열은 무조건 팰린드롬
for i in range(N):
    C[i][i] = True

# 길이가 2인 배열은 시작과 끝이 동일하면 팰린드롬
for i in range(N-1):
    if A[i] == A[i+1]:
        C[i][i+1] = True

# 길이가 3이상인 배열은 
# 1) 시작과 끝이 동일하며,
# 2) 시작과 끝을 제외한 배열이 팰린드롬이면 팰린드롬
for len in range(2, N):
    for i in range(N-len):
        if A[i]==A[i+len] and C[i+1][i+len-1]:
            C[i][i+len] = True

for m in range(M):
    S, E = map(int, input().split())
    if C[S-1][E-1]:
        answer.append("1")
    else:
        answer.append("0")

print("\n".join(answer))