길이가 N인 문자열 'str'이 주어졌다고 가정해 봅시다. 이때 주어진 이진 문자열(Binary String)에서 '1'로 시작하고 '1'로 끝나는 부분 문자열의 개수를 세는 것이 목표입니다. 이진 문자열은 '0'과 '1'만으로 구성된 문자열을 의미합니다.
입력 및 출력 예시
예시 1
N = 5 str = "11101"
출력: 6
설명: 주어진 이진 문자열에는 '1'로 시작하고 '1'로 끝나는 부분 문자열이 총 6개 존재합니다. 해당 부분 문자열의 집합은 {'11', '111', '1110', '11101', '1101', '101'}입니다.
예시 2
N = 4 str = "0011"
출력: 1
설명: 주어진 이진 문자열에서 조건을 만족하는 부분 문자열은 {'11'} 단 하나뿐입니다.
문제 해결 접근 방식
주어진 문자열에서 '1'로 시작하고 '1'로 끝나는 부분 문자열의 개수를 구해야 합니다. 흥미롭게도 이 문제는 파티에 참석한 n명의 사람 사이에서 이루어지는 악수 횟수를 세는 유명한 핸드셰이크(Handshake) 문제와 동일한 원리로 해결할 수 있습니다.
핵심 아이디어는 매우 간단합니다. 문자열에 등장하는 '1'의 개수만 세면, '1'로 시작하고 '1'로 끝나는 모든 부분 문자열의 개수를 바로 도출할 수 있습니다. 두 개의 서로 다른 '1' 위치를 선택하는 모든 경우의 수가 곧 조건을 만족하는 부분 문자열의 개수가 되기 때문입니다.
알고리즘 단계
- 길이 N인 문자열을 입력받습니다.
- 정수형 함수 countSubstring(int N, string s)는 문자열의 길이와 문자열을 입력으로 받아 '1'로 시작하고 '1'로 끝나는 모든 부분 문자열의 개수를 반환합니다.
- 전체 문자열을 한 번 순회하면서 문자열 내 '1'의 개수를 셉니다.
- n*(n-1)/2 공식을 적용하여 가능한 쌍(pair)의 개수를 계산합니다.
- 계산 결과 n*(n-1)/2를 반환합니다.
C++ 코드 예제
#include<iostream>
using namespace std;
int countSubstring(int N, string s){
int count=0;
for(int i=0; s[i]!= '\0'; ++i){
if( s[i]== '1' )
count++;
}
return count*(count-1)/2;
}
int main() {
int N=5;
string str= "11101";
cout<< countSubstring(N,str)<<endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
6
주어진 문자열 "11101"에는 '1'이 총 4개 등장하므로(count = 4), 조건을 만족하는 부분 문자열의 총 개수는 4×(4−1)/2 = 6입니다. 이처럼 단순히 '1'의 개수를 세는 선형 탐색 O(N)만으로도 문제를 매우 효율적으로 해결할 수 있습니다.