Python으로 동일한 접두사와 접미사를 제거한 뒤 문자열의 최소 길이 구하기

문제 개요

문자열 s가 있으며, 이 문자열은 오직 세 가지 문자인 'a', 'b', 'c'로만 구성되어 있다고 가정해 보겠습니다. 우리는 다음 알고리즘을 원하는 만큼(0회 포함) 반복해서 적용할 수 있습니다.

모든 문자가 서로 같은 비어 있지 않은 접두사(prefix)를 선택합니다.
모든 문자가 서로 같은 비어 있지 않은 접미사(suffix)를 선택합니다.
선택한 접두사와 접미사는 서로 겹쳐서는 안 됩니다(disjoint).
접두사와 접미사를 구성하는 문자는 반드시 서로 같아야 합니다.
선택한 접두사와 접미사를 문자열 s에서 모두 제거합니다.

목표

위 연산을 임의의 횟수만큼 수행한 후(전혀 수행하지 않아도 됨), 남은 문자열 s의 최소 길이를 구하는 것이 목표입니다.

예를 들어 입력이 s = "aabccabba"라면 출력은 3입니다. 그 이유는 다음과 같습니다. 먼저 접두사 "aa"와 접미사 "a"를 선택해 제거하면 문자열은 "bccabb"가 됩니다. 이어서 접두사 "b"와 접미사 "bb"를 선택해 제거하면 문자열은 "cca"가 되고, 이때 길이는 3입니다.

해결 방법

이 문제는 덱(deque) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 양쪽 끝에서 요소를 빠르게 삭제할 수 있는 덱의 특성을 활용하는 것입니다. 핵심 아이디어는 다음과 같습니다.

문자열 s를 덱으로 변환합니다.
덱의 크기가 1보다 크고, 맨 앞 문자와 맨 뒤 문자가 서로 같은 동안 다음을 반복합니다.
- chk에 현재 맨 앞 문자를 저장합니다.
- 맨 앞 문자가 chk와 같은 동안 계속 왼쪽 요소를 삭제합니다.
- 덱이 비어 있지 않고, 맨 뒤 문자가 chk와 같은 동안 계속 마지막 요소를 삭제합니다.
반복이 끝나면 덱의 크기를 반환합니다.

이 방식이 작동하는 이유는, 양끝 문자가 같다면 해당 문자로 된 접두사와 접미사를 한 번에 모두 제거하는 것이 항상 최적이기 때문입니다. 양끝이 다른 순간에는 더 이상 유효한 연산을 수행할 수 없으므로 반복이 종료됩니다.

구현 예제

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

from collections import deque
def solve(s):
   s = deque(s)
   while len(s) > 1 and s[0] == s[-1]:
      chk = s[0]
      while s and s[0] == chk:
         s.popleft()
      while s and s[-1] == chk:
         s.pop()
   return len(s)

s = "aabccabba"
print(solve(s))

입력

"aabccabba"

출력

정리

이 문제는 그리디(greedy) 관점에서 접근하면 간단히 해결됩니다. 양쪽 끝 문자가 일치하는 한, 해당 문자로 이루어진 모든 앞부분과 뒷부분을 제거하는 것이 최선의 선택입니다. 덱을 사용하면 양쪽 끝 삭제 연산이 O(1) 시간에 처리되므로, 전체 시간 복잡도는 문자열 길이에 비례하는 O(n)으로 매우 효율적입니다.