문제 설명
문자열 str이 주어졌다고 가정해 봅시다. 문자열의 경계(border)란 해당 문자열의 진접두사(proper prefix)이면서 동시에 접미사(suffix)가 되는 부분 문자열을 의미합니다. 예를 들어 'ab'는 문자열 'ababab'의 경계입니다. 이러한 경계가 회문(palindrome)이라면 이를 회문 경계(palindrome border)라고 부릅니다.
주어진 문자열 str의 회문 경계 개수를 f(str)이라고 할 때, str의 모든 비어 있지 않은 부분 문자열 str_k에 대해 f(str_k)의 총합을 구하는 것이 목표입니다. 결과값이 매우 커질 수 있으므로 10^9 + 7로 나눈 나머지를 계산합니다.
예를 들어 입력이 str = 'pqpqp'라면 출력은 5가 됩니다. 'pqpqp'에는 총 15개의 부분 문자열이 존재하지만, 회문 경계를 가지는 부분 문자열은 다음 4개뿐입니다:
pqp : f(pqp) = 1 pqpqp : f(pqpqp) = 2 qpq : f(qpq) = 1 pqp : f(pqp) = 1 이 값들의 합은 1 + 2 + 1 + 1 = 5입니다.
풀이 접근 방법
이 문제는 세 가지 보조 함수와 메인 풀이 로직으로 해결할 수 있습니다.
1. palindrome_calculator() 함수
딕셔너리 input_dict를 입력받아 각 값(item2)에 대해 item2 × ((item2 − 1) / 2의 내림값)을 누적한 후 반환합니다. 즉, 동일한 회문이 n번 등장할 때 만들 수 있는 쌍의 개수를 계산합니다.
2. str_check() 함수
문자열의 모든 문자가 첫 번째 문자와 동일한지 검사합니다. 하나라도 다르면 False를, 모두 같으면 True를 반환합니다.
3. string_res() 함수
'aaaa'처럼 모든 문자가 동일한 특수한 경우를 처리합니다. i를 2부터 문자열 길이까지 반복하며 i × ((i − 1) / 2의 내림값)을 더하고, 매번 1000000007로 나눈 나머지를 적용한 뒤 결과를 반환합니다.
메인 풀이 로직
- str_check(string)이 True이면 string_res(string)을 바로 반환합니다.
- ans := 0으로 초기화합니다.
- 홀수 길이 처리: odd_list를 초기화한 후, 문자열의 각 문자 빈도를 딕셔너리에 기록하고 모든 인덱스를 리스트에 저장합니다. 길이 1인 회문(개별 문자)의 조합을 palindrome_calculator로 계산하여 ans에 더합니다.
- 짝수 길이 처리: even_list를 초기화한 후, 인접한 두 문자가 같은 위치 i를 찾아 저장하고 해당 2글자 부분 문자열의 빈도를 기록합니다. 역시 palindrome_calculator로 계산하여 ans에 더합니다.
- 길이 3 이상 확장: val을 3부터 문자열 길이 미만까지 반복합니다. val이 짝수면 even_list를, 홀수면 odd_list를 기준으로 사용합니다. 기존 회문의 시작 위치에서 양쪽으로 한 글자씩 확장했을 때 양 끝 문자가 서로 같으면 새로운 회문이 성립하므로, 새 위치와 부분 문자열 빈도를 new_t에 기록합니다. 각 단계마다 palindrome_calculator로 계산한 값을 ans에 더하고 1000000007로 나눈 나머지를 적용한 후, val의 홀짝성에 따라 even_list 또는 odd_list를 new_t로 갱신합니다.
- 모든 반복이 끝나면 최종 ans를 반환합니다.
구현 예제
다음 구현을 통해 더 잘 이해해 봅시다.
def palindrome_calculator(input_dict):
ans = 0
for item1, item2 in input_dict.items():
ans += item2 * (item2 - 1) // 2
return ans
def str_check(string):
t_str = string[0]
for s in string:
if s != t_str:
return False
return True
def string_res(string):
ans = 0
for i in range(2, len(string) + 1):
ans += i * (i - 1) // 2
ans %= 1000000007
return ans
def solve(string):
if str_check(string):
return string_res(string)
ans = 0
odd_list = [[], {}, 1]
for s in string:
if s not in odd_list[1]:
odd_list[1][s] = 0
odd_list[1][s] += 1
for i in range(len(string)):
odd_list[0].append(i)
ans += palindrome_calculator(odd_list[1])
even_list = [[], {}, 1]
for i in range(len(string) - 1):
if string[i] == string[i + 1]:
even_list[0].append(i)
tmp = string[i:i + 2]
if tmp not in even_list[1]:
even_list[1][tmp] = 0
even_list[1][tmp] += 1
ans += palindrome_calculator(even_list[1])
for val in range(3, len(string)):
if val % 2 == 0:
wt = even_list
else:
wt = odd_list
new_t = [[], {}, val]
for index in wt[0]:
if index - 1 >= 0 and index + val - 2 < len(string) and string[index - 1] == string[index + val - 2]:
new_t[0].append(index - 1)
tmp = string[index - 1 : index - 1 + val]
if tmp not in new_t[1]:
new_t[1][tmp] = 0
new_t[1][tmp] += 1
ans += palindrome_calculator(new_t[1])
ans %= 1000000007
if val % 2 == 0:
even_list = new_t
else:
odd_list = new_t
return ans
print(solve('pqpqp'))입력
'pqpqp'
출력
5