파이썬으로 서로 다른 인접 비트 쌍 제거 후 최소 문자열 길이 구하기

이진 문자열(binary string) s가 주어졌다고 가정해 봅시다. 우리는 서로 다른 두 개의 인접한 문자가 있을 때, 그 쌍을 삭제할 수 있습니다. 이 연산을 원하는 만큼 반복했을 때, 최종적으로 얻을 수 있는 가장 짧은 문자열의 길이를 구하는 것이 목표입니다.

예를 들어 입력이 s = "1100011"이라면 결과는 1이 됩니다.

• "10"을 삭제 → "10011"
• 다시 "10"을 삭제 → "011"
• "01"을 삭제 → "1" 남음

접근 방법: 스택(Stack) 활용

이 문제는 스택 자료구조를 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 빈 스택(리스트)을 하나 생성합니다.
• 문자열의 각 문자 c를 순서대로 확인합니다.
  • 스택이 비어 있거나, 스택의 최상단(top) 문자가 c와 같다면 → c를 스택에 push 합니다.
  • 스택의 최상단 문자가 c와 다르다면 → 스택에서 요소를 pop 합니다. (인접한 다른 문자 쌍이 제거되는 것과 동일한 효과)
• 모든 문자를 처리한 후, 스택에 남아 있는 요소의 개수를 반환합니다.

pop 연산 한 번은 곧 서로 다른 인접 문자 쌍 하나를 제거하는 것과 같으므로, 마지막에 스택에 남은 문자들이 바로 더 이상 제거할 수 없는 최소 상태의 문자열이 됩니다.

구현 예제

class Solution:
   def solve(self, s):
      stack = []
      for c in s:
         if not stack or stack[-1] == c:
            stack.append(c)
         elif stack[-1] != c:
            stack.pop()
      return len(stack)
ob = Solution()
print(ob.solve("1100011"))

입력

"1100011"

출력

1

복잡도 분석

• 시간 복잡도: O(n) — 문자열의 각 문자를 한 번씩만 확인하면 됩니다.
• 공간 복잡도: O(n) — 최악의 경우 모든 문자가 스택에 저장될 수 있습니다.

이처럼 스택을 활용하면 문자를 직접 삭제하고 재배열하는 복잡한 시뮬레이션 없이도 선형 시간 안에 정답을 구할 수 있습니다.