문제 개요
하나의 문자열이 주어졌을 때, 이 문자열 안에 존재하는 회문(palindrome) 부분 문자열의 개수를 세는 문제입니다. 여기서 시작 인덱스 또는 끝 인덱스가 다르면, 문자 구성이 완전히 같더라도 서로 다른 부분 문자열로 간주한다는 점이 중요합니다.
예를 들어 입력이 "aaa"라면, "a", "a", "a", "aa", "aa", "aaa"처럼 총 6개의 회문 부분 문자열이 존재하므로 정답은 6이 됩니다.
해결 접근 방법
가장 직관적인 풀이는 만들 수 있는 모든 부분 문자열을 하나씩 생성한 뒤, 각각이 회문인지 검사하는 것입니다. 알고리즘의 흐름은 다음과 같습니다.
- count를 0으로 초기화합니다.
- i를 0부터 문자열 길이까지 반복합니다.
- j를 i+1부터 문자열 길이+1까지 반복합니다.
- temp에 인덱스 i부터 j까지의 부분 문자열을 저장합니다.
- temp가 회문이라면 count를 1 증가시킵니다.
- j를 i+1부터 문자열 길이+1까지 반복합니다.
- 최종적으로 count를 반환합니다.
회문 판별 방법
파이썬에서는 슬라이싱 기법인 s[::-1]을 활용하면 문자열을 아주 간단하게 뒤집을 수 있습니다. 원본 문자열과 뒤집은 문자열이 서로 같다면 그 문자열은 회문입니다.
예제 코드(Python)
아래 예제를 통해 실제 구현 과정을 자세히 살펴보겠습니다.
class Solution:
def countSubstrings(self, s):
counter = 0
for i in range(len(s)):
for j in range(i+1,len(s)+1):
temp = s[i:j]
if temp == temp[::-1]:
counter+=1
return counter
ob1 = Solution()
print(ob1.countSubstrings("aaaa"))
입력
"aaaa"
출력
10
시간 복잡도 분석
모든 부분 문자열을 생성하는 데 O(n²)의 시간이 걸리고, 각 부분 문자열의 회문 여부를 확인하는 데 최대 O(n)이 소요됩니다. 따라서 위 코드의 전체 시간 복잡도는 O(n³)입니다. 입력 문자열이 매우 긴 경우에는 중심 확장법(expand around center)이나 Manacher's 알고리즘처럼 O(n²) 이하로 동작하는 최적화 기법을 함께 고려하는 것이 좋습니다.