[Bronze I] 더블팰린드롬 - 32357

문제 링크

성능 요약

메모리: 32412 KB, 시간: 4160 ms

분류

수학, 구현, 문자열, 애드 혹

제출 일자

2025년 2월 16일 20:23:53

문제 설명

종현은 알고리즘 과제로 팰린드롬에 대해서 공부하고 있다. 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 문자열을 말한다. 예를 들어 'abba', 'level' 등은 팰린드롬이며 'abab', 'boj' 등은 팰린드롬이 아니다.

종현은 팰린드롬을 보다가 새로운 현상을 발견하게 되었다. 먼저, 길이가 짝수인 문자열 $X$, $Y$를 고른다. 그리고 $X$를 같은 길이의 두 부분으로 나누어 문자열 $X_1$, $X_2$를 얻는다. 다음으로 종현은 $X_1$, $Y$와 $X_2$를 순서대로 이어 붙여 새로운 문자열 $Z$를 얻는다. 이렇게 얻은 $Z$가 팰린드롬이라면 종현은 $X$와 $Y$가 더블팰린드롬 현상을 일으킨다고 부르기로 했다.

길이가 짝수인 $N$개의 서로 다른 문자열 $s_1$, $s_2$, $...$, $s_N$이 주어질 때, $X=s_i$와 $Y=s_j$가 더블팰린드롬 현상을 일으키게 하는 두 정수 $i$,$j$의 쌍 $(i$, $j)$의 개수를 구해보자.

입력

첫 번째 줄에 문자열의 개수 $N$이 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐 길이가 짝수인 알파벳 소문자로만 구성된 문자열 $s_1$, $s_2$, $...$, $s_N$이 주어진다.

출력

더블팰린드롬 현상을 일으킬 수 있는 쌍의 개수를 출력한다.

---

💡 해결 방법

💻 코드

# 종현은 알고리즘 과제로 팰린드롬에 대해서 공부하고 있다. 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 문자열을 말한다. 예를 들어 'abba', 'level' 등은 팰린드롬이며 'abab', 'boj' 등은 팰린드롬이 아니다.
 
# 종현은 팰린드롬을 보다가 새로운 현상을 발견하게 되었다. 먼저, 길이가 짝수인 문자열 
# $X$, 
# $Y$를 고른다. 그리고 
# $X$를 같은 길이의 두 부분으로 나누어 문자열 
# $X_1$, 
# $X_2$를 얻는다. 다음으로 종현은 
# $X_1$, 
# $Y$와 
# $X_2$를 순서대로 이어 붙여 새로운 문자열 
# $Z$를 얻는다. 이렇게 얻은 
# $Z$가 팰린드롬이라면 종현은 
# $X$와 
# $Y$가 더블팰린드롬 현상을 일으킨다고 부르기로 했다.
 
 
 
# 길이가 짝수인 
# $N$개의 서로 다른 문자열 
# $s_1$, 
# $s_2$, 
# $...$, 
# $s_N$이 주어질 때, 
# $X=s_i$와 
# $Y=s_j$가 더블팰린드롬 현상을 일으키게 하는 두 정수 
# $i$,
# $j$의 쌍 
# $(i$, 
# $j)$의 개수를 구해보자.
 
# 입력
# 첫 번째 줄에 문자열의 개수 
# $N$이 주어진다.
 
# 두 번째 줄부터 
# $N$개의 줄에 걸쳐 길이가 짝수인 알파벳 소문자로만 구성된 문자열 
# $s_1$, 
# $s_2$, 
# $...$, 
# $s_N$이 주어진다.
 
# 출력
# 더블팰린드롬 현상을 일으킬 수 있는 쌍의 개수를 출력한다.
 
# 제한
#  
# $2 \le N \le 10\,000$
#  
# $1 \le i \le N$
#  
# $1 \le j \le N$
#  
# $i \neq j$ 
# 입력으로 주어지는 모든 수는 정수이다.
# 입력으로 주어지는 문자열의 길이는 
# $1\,000$ 이하이며 짝수이다.
# 입력으로 주어지는 문자열은 중복되지 않는다.
# 예제 입력 1 
# 3
# abba
# aa
# ac
# 예제 출력 1 
# 2
 
 
#단순 팰린 + 펠린 > 더블팰린드롬, i랑 j랑 중복 안되는데 순서는 바꿀수 있음, x개의 펠린드롬? > x p 2 >
 
count = 0
 
n = int(input())
 
 
for i in range(0 , n):
    nums = list(input())
    for i2 in range(0, len(nums)):
        if nums[i2] != nums[len(nums) - 1 - i2]:#반대쪽과 검사
            break
        if i2 == int(len(nums)) - 1:#길이 4면 1, 즉 검사의 마지막까지 break안됨, 즉 펠린드롬
            count += 1
            break
 
#이시점에서, count에는 입력 문자열중에펠린드롬의 개수가 들어가 있다, 이 이후 count P 2를 출력하면 끝
 
 
ans1 = 1
 
for i in range(1, count+1):
    ans1 *= i
 
 
 
ans2 = 1
for i in range(1, (count - 2)+1):
    ans2 *= i
 
if count < 2:
    print(0)
else:
    print(int(ans1 / ans2), end = '')