C++로 이진 문자열에서 최소 올바른 문자열 찾기

n비트로 구성된 이진 문자열 S가 있다고 가정해 보겠습니다. 이 문자열에는 불필요한 선행 0(leading zero)이 없습니다. 우리는 S에 대해 다음 두 가지 연산을 수행할 수 있습니다.

• 인접한 두 비트의 위치를 서로 교환(swap)
• 문자열에 있는 모든 "11"을 "1"로 치환

val(S)를 S의 10진수 값이라고 정의할 때, 올바른(correct) 문자열 A가 다른 올바른 문자열 B보다 작다는 것은 val(A) < val(B)일 때를 의미합니다. 우리의 목표는 주어진 조건에서 만들 수 있는 가장 작은 올바른 문자열을 찾는 것입니다.

예를 들어 입력이 S = "1001"이라면 출력은 100이 됩니다. "1001" → "1010" → "1100" → "100" 순서로 연산을 수행할 수 있기 때문입니다.

풀이 접근 방식

핵심 아이디어는 간단합니다. 인접 비트 교환 연산을 반복적으로 사용하면 모든 1을 문자열의 맨 앞으로 몰아낼 수 있고, 이후 "11"을 "1"로 치환하는 연산을 적용하면 결국 첫 번째 비트의 1 하나만 남게 됩니다. 따라서 최종 결과 문자열은 원래 문자열의 첫 번째 비트와, 나머지 자리에 존재했던 모든 0으로 구성됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

n := S의 길이
res := 빈 문자열
res := res + S[0]  // 첫 번째 비트 추가
for i := 1 부터 n-1 까지 반복:
    if S[i]가 '0'이면:
        res := res + "0"
return res

예제 코드 (C++)

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

#include <bits/stdc++.h>
using namespace std;
string solve(string S){
   int n = S.size();
   string res = "";
   res += S[0];
   for (int i = 1; i < n; i++){
      if (S[i] == '0'){
         res += "0";
      }
   }
   return res;
}
int main(){
   string S = "1001";
   cout << solve(S) << endl;
}

입력

"1001"

출력

100

복잡도 분석

이 알고리즘은 문자열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)이며, 결과 문자열을 저장하기 위한 공간 복잡도 역시 O(n)입니다. 입력 크기와 무관하게 선형 시간 안에 효율적으로 동작합니다.