특수 이진 문자열이란?
먼저 특수 이진 문자열(Special Binary String)의 정의를 살펴보겠습니다. 어떤 이진 문자열이 다음 두 가지 조건을 만족하면 특수 문자열이라고 합니다.
- 문자열 내에 0과 1의 개수가 동일해야 합니다.
- 문자열의 모든 접두사(prefix)에서 1의 개수가 0의 개수보다 크거나 같아야 합니다.
문제 설명
특수 문자열 S가 주어졌을 때, 하나의 '이동(move)'은 S에서 서로 인접한 두 개의 비어 있지 않은 특수 부분 문자열을 골라 서로 맞바꾸는 것을 의미합니다.
우리의 목표는 이러한 이동을 임의의 횟수만큼 수행한 뒤 얻을 수 있는 결과 문자열 중 사전순(lexicographically)으로 가장 큰 문자열을 찾는 것입니다.
예시
입력이 11011000이라면 출력은 11100100이 됩니다. 그 이유는 부분 문자열 "10"과 "1100"을 서로 교환하면 사전순으로 가장 큰 문자열을 만들 수 있기 때문입니다.
해결 전략
이 문제는 재귀(recursion)와 정렬(sorting)을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 주어진 문자열을 더 이상 분할할 수 없는 원시(primitive) 특수 부분 문자열들로 나눕니다. 카운터(cnt)를 사용해 '1'을 만나면 증가시키고 '0'을 만나면 감소시키며, 카운터가 0이 되는 지점이 하나의 원시 문자열의 경계입니다.
- 각 원시 부분 문자열의 안쪽 부분에 대해 재귀적으로 같은 함수를 호출하여 최적화합니다.
- 모든 부분 문자열을 내림차순으로 정렬한 뒤 이어 붙이면 사전순으로 가장 큰 결과를 얻을 수 있습니다.
알고리즘 단계
- 함수
makeLargestSpecial(s)를 정의합니다. - 결과를 담을 빈 문자열 ret과 문자열 배열 v를 준비합니다.
- 인덱스 i를 0으로 초기화하고, j와 cnt를 0부터 시작해 문자열을 순회합니다.
- s[j]가 '1'이면 cnt를 증가시키고, '0'이면 감소시킵니다.
- cnt가 0이 되면, 해당 구간을 "1" + 재귀 호출 결과 + "0" 형태로 만들어 v에 추가하고 i를 갱신합니다.
- v를 내림차순으로 정렬한 후 모든 요소를 ret에 이어 붙여 반환합니다.
- 메인 함수에서 주어진 문자열로
makeLargestSpecial()을 호출합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string makeLargestSpecial(string s) {
string ret = "";
vector<string> v;
int i = 0;
for (int j = 0, cnt = 0; j < s.size(); j++) {
if (s[j] == '1') {
cnt++;
}
else
cnt--;
if (cnt == 0) {
v.push_back("1" + makeLargestSpecial(s.substr(i + 1,
j - i - 1)) + "0");
i = j + 1;
}
}
sort(v.rbegin(), v.rend());
for (int i = 0; i < v.size(); i++)
ret += v[i];
return ret;
}
};
main(){
Solution ob;
cout << (ob.makeLargestSpecial("11011000"));
}입력
11011000
출력
11100100
마무리
이 알고리즘은 문자열을 원시 특수 부분 문자열 단위로 분해한 뒤, 각 부분을 재귀적으로 최적화하고 내림차순 정렬을 통해 결합하는 방식으로 동작합니다. 시간 복잡도는 일반적으로 O(n² log n) 수준으로 평가되며, 재귀적 분할 정복 기법이 이진 문자열 문제에 얼마나 효과적인지 잘 보여주는 대표적인 예제입니다.