괄호로만 이루어진 문자열들이 주어졌을 때, 이들을 서로 짝지어 균형이 맞는(balanced) 괄호 시퀀스를 몇 쌍 만들 수 있는지 계산하는 것이 이번 문제의 목표입니다.
여기서 '균형이 맞는다'는 것은 여는 괄호 '('와 닫는 괄호 ')'의 개수가 서로 같다는 의미입니다. 단, 한 번 사용된 괄호 문자열은 다른 쌍을 만들 때 다시 사용할 수 없습니다.
입력·출력 예시
입력 − string paran[] = { ")()())", "(", ")(", ")(", ")" }
출력 − 균형 잡힌 괄호 시퀀스 쌍의 개수: 1
설명 − 각 문자열 요소를 하나씩 살펴보며 쌍의 개수를 계산해 보겠습니다. 첫 번째 요소 ")()())"에는 닫는 괄호가 4개, 여는 괄호가 2개 들어 있으므로, 이를 균형 잡히게 만들려면 정확히 여는 괄호 2개분을 보충해 줄 수 있는 문자열이 필요합니다. 하지만 배열 어디에도 그런 문자열이 없으므로 이 요소는 제외하고 다음으로 넘어갑니다. 결국 여는 괄호와 닫는 괄호의 개수가 정확히 일치하는 유효한 쌍은 (2, 5), 즉 "(" 와 ")" 의 조합 하나뿐이므로 결과는 1이 됩니다.
입력 − string paran[] = { ")()())", "((", "(", ")(", ")(", ")" }
출력 − 균형 잡힌 괄호 시퀀스 쌍의 개수: 2
설명 − 이 경우에는 유효한 균형 쌍이 (1, 2)와 (3, 6) 두 곳에서 성립하므로 결과는 2가 됩니다.
알고리즘 접근 방식
- 문자열 배열을 입력받고 length() 함수로 각 문자열의 길이를 구한 뒤, 이후 처리를 위해 함수에 데이터를 전달합니다.
- 유효한 괄호 쌍의 개수를 저장할 임시 변수 count를 선언하고, unordered_map 타입의 um_1과 um_2 변수를 생성합니다.
- 0부터 배열 크기까지 반복하는 FOR 루프를 시작합니다.
- 루프 안에서 str을 paran[i], 즉 현재 검사할 괄호 문자열로 설정하고 해당 문자열의 길이를 다시 계산합니다.
- 임시 변수 first와 last를 선언하고 0으로 초기화합니다.
- j를 0부터 문자열 길이까지 반복하는 FOR 루프를 시작합니다.
- 루프 안에서 str[j]가 '('라면 first를 1 증가시키고, 그렇지 않은 경우 first가 남아 있으면 first를 1 감소시키고, 그 외의 경우에는 last를 1 증가시킵니다.
- 문자열 순회가 끝난 후, first가 0이 아니고 last가 0이면 um_1[first]를 증가시킵니다(순수하게 남는 여는 괄호). 반대로 last가 0이 아니고 first가 0이면 um_2[last]를 증가시킵니다(순수하게 남는 닫는 괄호). first와 last가 모두 0이라면 이 문자열 자체가 이미 균형을 이루는 것이므로 count를 1 증가시킵니다.
- 자체 균형 문자열은 두 개가 모여 한 쌍을 이루므로 count를 count / 2로 나눕니다.
- um_1을 순회하면서 count에 min(um_1의 값, um_2의 대응 값)을 더해 서로 보완 가능한 쌍의 개수를 누적합니다.
- 최종 count를 반환하고 결과를 출력합니다.
예제 코드
#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