Python으로 모든 A가 B보다 앞에 오도록 만들기 위해 삭제해야 하는 최소 문자 수 구하기

문제 설명

'A'와 'B' 두 글자로만 구성된 문자열 s가 있다고 가정해 보겠습니다. 이때, 문자열 내의 모든 'A'가 모든 'B'보다 앞쪽에 위치하도록 만들기 위해 삭제해야 하는 최소 문자 수를 구하는 프로그램을 작성해야 합니다.

예를 들어 입력이 S = "AABAABB"라면, 마지막 'A' 하나만 제거하면 "AABBB"가 되어 조건을 만족할 수 있으므로 출력은 1이 됩니다.

접근 방법

이 문제는 분할 지점(split point)을 기준으로 왼쪽의 'B' 개수와 오른쪽의 'A' 개수를 추적하는 그리디 방식으로 해결할 수 있습니다. 특정 지점을 기준으로 정렬한다면, 해당 지점 왼쪽에 있는 'B'들과 오른쪽에 있는 'A'들을 제거해야 하므로, 두 값의 합이 최소가 되는 지점을 찾으면 됩니다.

구체적인 해결 단계는 다음과 같습니다:

a_right := 문자열 s에서 'A'의 총 개수
b_left := 0
ans := a_right (모든 'B'를 제거하는 경우를 초기값으로 설정)
문자열의 각 인덱스 i와 문자 c에 대해 반복:
- c가 'A'와 같다면 → a_right를 1 감소 (현재 위치 기준 오른쪽에 남은 'A' 개수)
- 그렇지 않다면 → b_left를 1 증가 (현재 위치 기준 왼쪽에 있는 'B' 개수)
- ans := ans와 (a_right + b_left) 중 더 작은 값으로 갱신
ans 반환

각 위치를 순회하면서 '분할 지점'을 옮겨가며 최소 삭제 횟수를 계산하는 방식입니다. 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

예제 코드

아래 구현을 통해 더 잘 이해해 보겠습니다:

class Solution:
   def solve(self, s):
      a_right = s.count("A")
      b_left = 0

      ans = a_right
      for i, c in enumerate(s):
         if c == "A":
            a_right -= 1
         else:
            b_left += 1
         ans = min(ans, a_right + b_left)
      return ans

ob = Solution()
S = "AABAABB"
print(ob.solve(S))

입력

"AABAABB"