문자열 text가 주어졌을 때, 다음 세 가지 조건을 모두 만족하는 최댓값 k를 찾는 문제입니다.
- 각 a[i]는 비어 있지 않은(non-empty) 문자열이어야 합니다.
- a[1] + a[2] + ... + a[k]의 연결 결과가 주어진 text와 같아야 합니다.
- 모든 i(1 ≤ i ≤ k)에 대해 a[i] = a[k+1-i]가 성립해야 합니다. 즉, 앞쪽에서 i번째 조각과 뒤쪽에서 i번째 조각이 서로 같은 문자열이어야 합니다.
예를 들어 입력이 "antaprezatepzapreanta"라면 출력은 11이 됩니다. 이 문자열은 다음과 같이 11개의 대칭 조각으로 나눌 수 있기 때문입니다.
(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)
접근 방법
이 문제는 양쪽 끝에서부터 조각을 하나씩 늘려가며 비교하는 그리디(greedy) 방식으로 해결할 수 있습니다. 왼쪽에서 잘라낸 접두사와 오른쪽에서 잘라낸 접미사가 일치하는 순간마다 두 개의 조각을 확정하고, 정답 카운트를 2씩 증가시킵니다. 전체 과정은 다음과 같습니다.
- start := 0, end := len(text) - 1 로 초기화합니다.
- temp1과 temp2를 빈 문자열로 초기화합니다.
- ans는 text 길이가 홀수면 1, 짝수면 0으로 시작합니다. (길이가 홀수인 경우 가운데 남는 한 조각을 미리 계산)
- start < end 인 동안 반복합니다.
- temp1 := temp1 + text[start] — 왼쪽 조각을 한 글자씩 늘립니다.
- temp2 := text[end] + temp2 — 오른쪽 조각도 한 글자씩 늘립니다.
- 만약 temp1 == temp2 라면:
- temp1과 temp2를 빈 문자열로 초기화합니다.
- ans := ans + 2 (양쪽 조각이 하나씩 확정됨)
- start := start + 1, end := end - 1 로 포인터를 안쪽으로 이동합니다.
- 반복 종료 후, text 길이가 짝수이면서 temp1 또는 temp2가 비어 있지 않다면 ans := ans + 1 합니다. (가운데에 남은 조각 처리)
- ans를 반환합니다.
구현 예제
class Solution(object):
def longestDecomposition(self, text):
start = 0
end = len(text)-1
temp1 = ""
temp2 = ""
ans = 1 if len(text) & 1 else 0
while start<end:
temp1+=text[start]
temp2 = text[end]+temp2
if temp1 == temp2:
temp1 = temp2 = ""
ans+=2
start+=1
end-=1
if len(text)%2 == 0 and(temp1 or temp2):
ans += 1
return ans
ob = Solution()
print(ob.longestDecomposition("antaprezatepzapreanta"))입력
"antaprezatepzapreanta"
출력
11
동작 원리 정리
위 코드는 매 순간 가능한 한 작은 조각을 먼저 확정하는 그리디 전략을 사용합니다. 직관적으로 생각하면, 더 작은 조각을 일찍 잘라낼수록 이후에 더 많은 조각으로 나눌 여지가 생기므로 이 전략이 항상 최적의 답을 보장합니다. 시간 복잡도는 각 위치에서 문자열 비교가 발생하므로 최악의 경우 O(n²)이며, 공간 복잡도는 O(n)입니다.