괄호가 포함된 문자열이 주어지고 괄호가 균형을 이루도록 구성할 수 있는 괄호 시퀀스 쌍의 수를 계산하는 작업입니다.
여는 괄호와 닫는 괄호의 수가 같을 때 괄호가 균형을 이룬다고 합니다. 한 번 사용된 괄호는 쌍을 형성하는 데 두 번 고려될 수 없습니다.
입력 - 문자열 paran[] ={ ")()())", "(", ")(", ")(", ")" }
출력 − 괄호가 균형을 이루는 괄호 시퀀스 쌍의 개수는 다음과 같습니다. 1
설명 - 카운트를 더 잘 계산하기 위해 모든 문자열 세트를 사용합니다. 첫 번째 요소를 닫는 괄호 4개와 여는 괄호 2개가 있는 ")()()"로 간주하여 다음 요소가 아닌 균형 잡힌 괄호 시퀀스를 만들기 위해 정확히 2개의 닫는 괄호를 포함하는 문자열에서 다음 요소를 찾습니다. 그래서 우리는 그것을 버리고 다음으로 넘어갈 것입니다. 따라서 여는 괄호와 닫는 괄호가 같은 유효한 쌍은 (2, 5)이므로 개수는 1입니다.
입력 - 문자열 paran[] ={ ")()())", "((", "(", ")(", ")(", ")"}
출력 − 괄호가 균형을 이루는 괄호 시퀀스 쌍의 개수는 다음과 같습니다. 1
설명 - 유효한 균형 괄호 쌍은 (1, 2) 및 (3, 6)에 있습니다. 따라서 개수는 2입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
문자열을 입력하고 length() 함수를 사용하여 문자열의 길이를 계산하고 추가 처리를 위해 데이터를 함수에 전달합니다.
-
유효한 괄호 쌍을 저장하기 위해 임시 변수 개수를 사용하고 unordered_map 유형의 um_1 및 um_2 변수를 만듭니다.
-
0에서 문자열 크기까지 FOR 또 다른 루프 시작
-
루프 내에서 str을 paran[i], 즉 괄호의 첫 번째 요소로 설정하고 문자열의 길이를 다시 계산합니다.
-
임시 변수를 처음과 마지막으로 취하고 0으로 초기화합니다.
-
문자열의 길이까지 j에서 0까지 FOR 또 다른 루프 시작
-
루프 내에서 IF str[j] ='('를 확인한 다음 첫 번째 항목을 1씩 증가시킵니다. ELSE check IF first =1 다음 첫 번째 항목을 1 감소시키고 ELSE 마지막 항목을 1씩 증가시킵니다.
-
이제 IF first가 1이고 last가 0인지 확인한 다음 um_1[first]++를 설정하고 IF last가 1이고 first가 0인지 확인한 다음 um_2[lst]++를 설정하고 IF first가 0이고 last도 0인지 확인한 다음 카운트를 증가시킵니다. 1.
-
카운트를 카운트로 설정 / 2
-
0에서 um_1까지 루프를 시작하고 count를 um_1.second 및 um_2.first에서 최소값으로 설정
-
개수 반환
-
결과를 인쇄하십시오.
예
#include <bits/stdc++.h>
using namespace std;
int parentheses(string paran[], int size){
int count = 0;
unordered_map<int, int> um_1, um_2;
for (int i = 0; i < size; i++){
string str = paran[i];
int len = str.length();
int first = 0;
int last = 0;
for (int j = 0; j < len; j++){
if (str[j] == '('){
first++;
}
else{
if (first==1){
first--;
}
else{
last++;
}
}
}
if(first==1 && last!=1){
um_1[first]++;
}
if (last==1 && first!=1){
um_2[last]++;
}
if(first!=1 && last!=1){
count++;
}
}
count = count / 2;
for (auto it : um_1){
count += min(it.second, um_2[it.first]);
}
return count;
}
int main(){
string paran[] = { ")()())", "(", ")(", ")(", ")"};
int size = sizeof(paran) / sizeof(paran[0]);
cout<<"Count of pairs of parentheses sequences such that parentheses are balanced are:
"<<parentheses(paran, size);
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
Count of pairs of parentheses sequences such that parentheses are balanced are: 1