ps:problems:programmers:12904
가장 긴 팰린드롬
| ps | |
|---|---|
| 링크 | programmers.co.kr/… |
| 출처 | 프로그래머스 |
| 문제 번호 | 12904 |
| 문제명 | 가장 긴 팰린드롬 |
| 레벨 | Level 3 |
| 분류 |
Manacher |
| 시간복잡도 | O(n) |
| 인풋사이즈 | n<=2500 |
| 사용한 언어 | Python |
| 해결날짜 | 2021/07/04 |
풀이
- 가장 긴 팰린드롬 부분문자열 (Longest Palindromic Substring)을 참고. Manacher's algorithm을 이용해서 O(n)에 풀 수 있다.
코드
"""Solution code for "Programmers 12904. 가장 긴 팰린드롬".
- Problem link: https://programmers.co.kr/learn/courses/30/lessons/12904
- Solution link: http://www.teferi.net/ps/problems/programmers/12904
"""
from teflib import string
def solution(s):
return max(string.palindrome_radiuses('#' + '#'.join(s) + '#'))- Dependency: teflib.string.palindrome_radiuses
ps/problems/programmers/12904.txt · 마지막으로 수정됨: 2021/07/04 14:25 저자 teferi
토론