문제 개요
문자열 s가 주어졌을 때, 이 문자열에 포함된 모든 회문(palindrome) 부분 문자열의 길이가 홀수인지 확인하는 문제입니다.
예를 들어, 입력이 s = "levelopmadam"이라면 출력은 True가 됩니다. 이 문자열에는 "level"과 "madam"이라는 두 개의 회문 부분 문자열이 존재하며, 두 문자열 모두 길이가 5로 홀수이기 때문입니다.
접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 인덱스 i를 0부터 문자열 s의 길이까지 순회합니다.
- 임시 문자열 temp를 빈 문자열로 초기화합니다.
- 인덱스 j를 i부터 문자열 끝까지 순회하면서 temp에 s[j]를 한 글자씩 추가합니다.
- temp의 길이가 짝수이면서 동시에 회문이라면 조건을 만족하지 않으므로 즉시 False를 반환합니다.
- 모든 부분 문자열을 검사한 후에도 짝수 길이의 회문이 발견되지 않으면 True를 반환합니다.
구현 예제
def is_palindrome(s):
return s == s[::-1]
def solve(s):
for i in range(len(s)):
temp = ""
for j in range(i, len(s)):
temp += s[j]
if len(temp) % 2 == 0 and is_palindrome(temp):
return False
return True
s = "levelopmadam"
print(solve(s))
입력
"levelopmadam"
출력
True
코드 설명
is_palindrome 함수는 파이썬의 슬라이싱 기능(s[::-1])을 활용해 문자열을 뒤집은 결과와 원본을 비교함으로써 회문 여부를 판별합니다. 코드가 간결하면서도 직관적이라 가독성이 뛰어납니다.
solve 함수는 가능한 모든 시작 위치(i)와 끝 위치(j)의 조합을 탐색하며 부분 문자열을 생성합니다. 생성된 부분 문자열의 길이가 짝수이고 회문이라면 문제의 요구 조건을 위반하는 것이므로 False를 반환하고, 그렇지 않으면 검사를 계속 진행합니다.
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 O(n³)입니다. 부분 문자열을 생성하는 조합이 O(n²)개 존재하고, 각 회문 검사에 O(n)의 시간이 소요되기 때문입니다. 따라서 문자열이 길어질수록 실행 시간이 빠르게 증가합니다. 효율성이 중요한 대규모 입력에서는 중심 확장(center expansion) 기법이나 Manacher's Algorithm 같은 최적화된 방법을 함께 고려하는 것이 좋습니다.