이 튜토리얼에서는 이진 문자열을 01 또는 10 쌍으로부터 완전히 제거하기 위해 필요한 쌍의 총 개수를 찾는 프로그램을 작성해 보겠습니다. 먼저 예제를 살펴보겠습니다.
문제 이해하기
입력 − 101010001
출력 − 4
위 예제에서 이진 문자열을 01과 10 쌍으로부터 자유롭게 만들려면 총 4개의 쌍을 삭제해야 합니다.
모든 쌍을 삭제한 후 남는 결과 문자열은 0입니다.
접근 방법
핵심 아이디어는 간단합니다. 01과 10 쌍은 항상 하나의 '0'과 하나의 '1'로 구성됩니다. 따라서 만들 수 있는 최대 쌍의 개수는 0의 개수와 1의 개수 중 더 작은 값과 같습니다. 즉, 삭제해야 할 쌍의 총 개수는 count(0)과 count(1) 중 최솟값입니다.
해결 단계
- 이진 문자열을 초기화합니다.
- 문자열 내에서 0과 1의 개수를 각각 셉니다.
- 0의 개수와 1의 개수 중 최솟값을 출력합니다.
C++ 코드 예제
실제 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int findMinimumNumberOfDeletions(string str, int len) {
int zeroes_count = 0, ones_count = 0;
// 0과 1의 개수 세기
for (int i = 0; i < len; i++) {
if (str[i] == '0') {
zeroes_count++;
}
else {
ones_count++;
}
}
return min(zeroes_count, ones_count);
}
int main() {
string str = "101010001";
int len = str.length();
cout << findMinimumNumberOfDeletions(str, len) << endl;
return 0;
}실행 결과
위 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.
4
동작 원리 분석
입력 문자열 "101010001"에는 0이 5개, 1이 4개 포함되어 있습니다. min(5, 4) = 4이므로 정확히 4개의 쌍을 제거할 수 있으며, 마지막에 0 하나가 남게 됩니다.
이 알고리즘의 시간 복잡도는 O(n)으로, 문자열 길이에 비례하여 선형적으로 동작하므로 매우 효율적입니다. 공간 복잡도 역시 O(1)로 추가 메모리가 거의 필요하지 않습니다.
마무리
이번 튜토리얼에서는 이진 문자열에서 01, 10 쌍을 제거하는 문제를 간단한 카운팅 기법으로 해결했습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글 섹션에 남겨주세요.