문제 개요
이진 문자열 s와 두 개의 점수 값 zero_one, one_zero가 주어진다고 가정해 봅시다. 우리는 다음과 같은 연산을 수행할 수 있습니다.
- 부분 문자열 "01"을 삭제하고 zero_one점을 획득
- 부분 문자열 "10"을 삭제하고 one_zero점을 획득
이때, 연산을 원하는 만큼 반복했을 때 얻을 수 있는 최대 점수를 구하는 것이 목표입니다.
예를 들어, 입력이 s = "10100101", zero_one = 3, one_zero = 2라고 해보겠습니다. 이 경우 출력은 11이 됩니다. 그 이유는 다음과 같습니다.
- "01"을 세 번 제거하여 3 × 3 = 9점 획득
- 남은 문자열은 "10"이 되며, 이를 제거하여 추가로 2점 획득
- 총점: 9 + 2 = 11
해결 전략
이 문제는 스택(Stack) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 입력 문자열을 비트(bit) 리스트 A로 변환합니다.
- 만약 zero_one < one_zero라면, 두 값을 서로 교환(swap)하고 문자열의 모든 비트를 XOR 1 연산으로 뒤집습니다. 이렇게 하면 항상 더 높은 점수를 주는 패턴("01")을 우선 처리하는 형태로 문제를 통일할 수 있습니다.
- 정답 변수 ans를 0으로 초기화하고 빈 스택을 준비합니다.
- A의 각 비트 x에 대해 다음을 수행합니다.
- 스택이 비어 있지 않고, 스택의 top 값이 x보다 작다면(즉, "01" 패턴이 완성되면) pop하고 ans에 zero_one을 더합니다.
- 그렇지 않으면 x를 스택에 push합니다.
- 모든 순회가 끝난 후, 스택에는 "10" 패턴만 남게 됩니다. 따라서 스택에 남아 있는 0의 개수와 1의 개수 중 최솟값 × one_zero를 ans에 더합니다.
- ans를 반환합니다.
Python 구현 예제
아래 코드를 통해 실제 동작을 확인해 보겠습니다.
class Solution: def solve(self, S, zero_one, one_zero): A = list(map(int, S)) if zero_one < one_zero: zero_one, one_zero = one_zero, zero_one for i in range(len(A)): A[i] ^= 1 ans = 0 stack = [] for x in A: if stack and stack[-1] < x: stack.pop() ans += zero_one else: stack.append(x) ans += one_zero * min(stack.count(0), stack.count(1)) return ans ob = Solution() s = "10100101" zero_one = 3 one_zero = 2 print(ob.solve(s, zero_one, one_zero))
입력
"10100101", 3, 2
출력
11
복잡도 분석
- 시간 복잡도: O(n) — 문자열을 한 번만 순회하면 됩니다.
- 공간 복잡도: O(n) — 최악의 경우 모든 비트가 스택에 저장될 수 있습니다.
스택 기반의 탐욕적(greedy) 접근 방식 덕분에 이 알고리즘은 긴 이진 문자열에서도 매우 빠르게 최대 점수를 계산할 수 있습니다.