문제 설명
문자열 s가 주어졌을 때, 해당 문자열에 회문(palindrome)인 접두사(prefix)와 접미사(suffix)가 모두 존재하는지 확인하는 문제입니다.
예를 들어 입력이 s = "levelishighforracecar"라면, 앞부분의 "level"과 뒷부분의 "racecar"가 각각 회문이므로 결과는 True가 됩니다.
접근 방법
다음 단계를 따라 문제를 해결할 수 있습니다.
- 변수 l에 문자열 s의 길이를 저장합니다.
- i를 2부터 l까지 1씩 증가시키면서, s의 첫 번째 문자부터 i번째 문자까지의 부분 문자열이 회문인지 검사합니다. 회문을 발견하면 반복문을 빠져나옵니다.
- 끝까지 회문인 접두사를 찾지 못했다면 False를 반환합니다.
- 같은 방식으로 i를 2부터 l까지 증가시키면서, s의 뒤에서 i번째 위치부터 마지막 문자까지의 부분 문자열이 회문인지 검사합니다. 회문을 발견하면 True를 반환합니다.
- 모든 검사를 마쳐도 회문을 찾지 못하면 False를 반환합니다.
예제 코드
def is_palindrome(s):
return s == s[::-1]
def solve(s):
l = len(s)
for i in range(2, l + 1):
if is_palindrome(s[0:i]):
break
if i == (l + 1):
return False
for i in range(2, l + 1):
if is_palindrome(s[l - i : l]):
return True
return False
s = "levelishighforracecar"
print(solve(s))
동작 원리
is_palindrome 함수는 파이썬의 슬라이싱 기능(s[::-1])을 활용해 문자열을 뒤집은 뒤 원본과 비교하는 방식으로 회문 여부를 판별합니다. 별도의 라이브러리 없이 한 줄로 구현할 수 있어 매우 간결합니다.
solve 함수는 먼저 가장 짧은 회문 접두사를 찾고, 접두사가 존재하는 경우에만 회문 접미사의 존재 여부를 확인합니다. 두 조건이 모두 충족되어야 True를 반환합니다.
실행 결과
입력:
"levelishighforracecar"
출력:
True
복잡도 분석
부분 문자열을 추출하고 회문 여부를 검사하는 데 최대 O(n)의 시간이 걸리며, 이를 길이별로 최대 n번 반복하므로 전체 시간 복잡도는 O(n²)입니다. 부분 문자열 생성으로 인해 공간 복잡도는 O(n)입니다.