문제 이해하기
하나의 문자열 text가 주어졌을 때, 다음 조건을 모두 만족하는 가장 큰 정수 k를 찾는 것이 목표입니다.
- 각 a[i]는 비어 있지 않은(non-blank) 문자열이어야 합니다.
- 모든 조각을 이어 붙인 a[1] + a[2] + ... + a[k]가 원래 문자열 text와 정확히 일치해야 합니다.
- 모든 i(1 ≤ i ≤ k)에 대해 a[i] = a[k+1-i], 즉 앞에서 i번째 조각과 뒤에서 i번째 조각이 서로 같아야 합니다.
예를 들어 입력이 text = "antaprezatepzapreanta"라면 출력은 11입니다. 아래와 같이 분할하면 좌우 대칭이 되기 때문입니다.
a | nt | a | pre | za | tpe | za | pre | a | nt | a
풀이 접근 방법
이 문제는 두 개의 포인터(two pointers)를 활용한 그리디(greedy) 방식으로 해결할 수 있습니다. 왼쪽 끝과 오른쪽 끝에서부터 잘라낼 수 있는 가장 짧은 동일한 접두사·접미사 쌍을 찾아 하나씩 제거해 나가면, 결과적으로 최대 분할 개수를 얻을 수 있습니다.
알고리즘 단계
- 분할 개수를 세기 위한 변수 counter를 0으로 초기화합니다.
- i := 1, j := len(text) - 1 로 설정합니다. (i는 왼쪽 경계 후보, j는 오른쪽 경계 후보)
- ic := 0, jc := len(text) 로 설정합니다. (ic는 현재 왼쪽 확정 경계, jc는 현재 오른쪽 확정 경계)
- i ≤ j인 동안 반복합니다.
- text[ic:i](왼쪽 후보 구간)와 text[j:jc](오른쪽 후보 구간)가 같다면, 두 조각이 성립하므로 counter를 2 증가시키고 ic := i, jc := j로 경계를 확정합니다.
- i는 1 증가, j는 1 감소시켜 탐색 범위를 좁힙니다.
- 반복이 끝난 뒤 ic ≠ jc라면, 중앙에 아직 처리되지 않은 한 조각이 남아 있는 것이므로 counter를 1 더합니다.
- counter를 반환합니다.
구현 예제 코드
아래는 위 알고리즘을 파이썬으로 구현한 코드입니다.
def solve(text):
counter = 0
i, j = 1, len(text) - 1
ic, jc = 0, len(text)
while i <= j:
if text[ic:i] == text[j:jc]:
counter += 2
ic = i
jc = j
i += 1
j -= 1
if ic != jc:
counter += 1
return counter
text = "antaprezatepzapreanta"
print(solve(text))입력
antaprezatepzapreanta
출력
11
복잡도 분석
각 반복마다 부분 문자열 비교가 최대 O(n)만큼 걸릴 수 있으므로, 전체 시간 복잡도는 최악의 경우 O(n²)입니다. 공간 복잡도는 추가 배열 없이 포인터 몇 개만 사용하므로 O(1)입니다.