문제 설명
이번 문제에서는 0과 1로만 구성된 이진 문자열이 주어지며, 이 문자열의 모든 순열 중 1로 시작하는 순열의 총 개수를 구해야 합니다. 답이 매우 큰 값이 될 수 있으므로 1000000007(10^9 + 7)로 나눈 나머지 형태로 출력합니다.
입력 : str = "10101001001" 출력 : 210 입력 : str = "101110011" 출력 : 56
이 문제는 조합론(combinatorics)적 사고를 바탕으로 공식을 유도하면 비교적 간단하게 해결할 수 있습니다.
해결 접근 방식
먼저 문자열에 포함된 1의 개수와 0의 개수를 각각 세어야 합니다. 문자열의 길이를 L, 1의 개수를 n, 0의 개수를 m이라고 가정하면, 정답을 구하는 공식은 다음과 같습니다.
(L-1)! / ((n-1)! × m!)
순열이 반드시 1로 시작해야 하므로, 하나의 1을 맨 앞자리에 고정합니다. 그러면 남는 자리는 L-1개가 되고, 이곳에는 n-1개의 1과 m개의 0을 배열하게 됩니다. 전체 (L-1)!개의 경우의 수에서 같은 숫자끼리의 위치 교환으로 발생하는 중복을 제거하기 위해 (n-1)!과 m!으로 나누는 원리입니다.
C++ 구현 예제
#include <bits/stdc++.h>
#define MOD 1000000007 // defining 1e9 + 7 as MOD
using namespace std;
long long fact(long long n) {
if(n <= 1)
return 1;
return ((n % MOD) * (fact(n-1) % MOD)) % MOD;
}
int main() {
string s = "101110011";
long long L = s.size(); // length of given string
long long count_1 = 0, count_0 = 0; // keeping count of 1's and 0's
for(auto x : s) {
if(x == '1')
count_1++; // frequency of 1's
else
count_0++; // frequency of 0's
}
if(count_1 == 0){
cout << "0\n"; // if string only consists of 0's so our answer will be 0
} else {
long long factL = fact(L-1); // (L-1)!
long long factn = fact(count_1 - 1); // (n-1)!
long long factm = fact(count_0); // m!
long long ans = factL / (factn * factm); // putting the formula
cout << ans << "\n";
}
return 0;
}실행 결과
56
위 프로그램의 시간 복잡도는 O(N)입니다. 여기서 N은 주어진 문자열의 길이입니다.
코드 상세 설명
이 접근 방식에서는 먼저 문자열 내부에 있는 1과 0의 개수를 계산합니다. 첫 번째 자리에 1을 하나 고정한 뒤, 길이 L-1인 나머지 부분에서 만들 수 있는 모든 순열을 공식으로 표현합니다. 그 결과 도출되는 식이 (L-1)! / ((n-1)! × m!)이며, 여기서 (n-1)!은 남은 1들의 중복 순열을, m!은 0들의 중복 순열을 처리하는 역할을 합니다.
전체적인 코드 흐름을 정리하면 다음과 같습니다.
- 문자열을 한 글자씩 순회하며 1의 빈도(count_1)와 0의 빈도(count_0)를 셉니다.
- 문자열에 1이 하나도 없다면, 어떤 순열도 1로 시작할 수 없으므로 정답은 0입니다.
- 1이 존재한다면 (L-1)!, (n-1)!, m!을 각각 계산한 후 공식에 대입하여 최종 결과를 출력합니다.
결론
이번 글에서는 조합론을 적용하고 공식을 직접 유도하여, 이진 문자열에서 1로 시작하는 고유 순열의 개수를 구하는 문제를 해결했습니다.
또한 이 문제를 해결하기 위한 C++ 프로그램과 함께 일반적인 접근 방식도 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 충분히 구현할 수 있습니다. 이 글이 독자 여러분께 도움이 되기를 바랍니다.