19.4문제:짝이 맞지 않는 괄호(ID:BRACKETS2)
문제
소녀시대학교 수학과의 류화영 교수는 이번에 다 쓴 논문을 훑어보던 중, 수식에 포함된 괄호들이 제대로 짝이 맞지 않는다는 사실을 발견했습니다. 완벽주의자인 류 교수는 컴퓨터 프로그램을 이용해 논문에 포함된 모든 수식들의 괄호가 쌍이 잘 맞는지 확인하기로 했습니다. 류 교수는 논문에 다음과 같은 세 종류의 괄호를 사용했습니다.
- 둥근 괄호는 ( 로 열고, ) 로 닫습니다.
- 중괄호는 { 로 열고, } 로 닫습니다.
- 대괄호는 [ 로 열고, ]로 닫습니다.
수식에 있는 괄호들이 다음과 같은 성질을 모두 만족할 때 해당 수식이 '짝이 맞는다'라고 표현합니다.
- 모든 괄호는 해당하는 짝이 있어야 합니다. 이때 ( 는 ) 와, { 는 } 와, [ 는 ] 와 짝을 이뤄야만 합니다.
- 모든 괄호 쌍은 먼저 열린 뒤 닫힙니다.
- 한 괄호 쌍이 다른 괄호쌍과 서로 '교차해'있으면 안 됩니다. 이 정의에 의하면 [(])는 짝이 맞지 않는 경우입니다.
입력받은 수식들이 짝이 잘 맞는지 확인하는 프로그램을 작성해 류 교수를 도와줍시다. 문제를 간단하게 하기 위해, 입력되는 수식에서 괄호 외의 문자는 모두 지웠습니다.입력
입력의 첫 줄에는 테스트 케이스의 수 C(1≤C≤100)가 주어집니다. 그 후 C 줄에 각 하나의 문자열로 테스트 케이스가 주어집니다. 이 문자열은 공백 없이 "(){}[]"에 포함된 글자로만 주어지며, 길이는 1이상 10,000 이하입니다.
출력
각 테스트 케이스마다, 주어진 괄호 문자열이 짝이 잘 맞는다면 "YES"를, 안 맞는다면 "NO"를 한 줄에 출력합니다.
예제 입력
3 ()() ({[}]) ({}[(){}])예제 출력
YES NO YES
First Thoughts
열린 괄호와 닫힌 괄호의 구분
괄호의 종류에는 크게 두 가지가 있는데 이는 열린 괄호와 닫힌 괄호로 나눌 수 있다. 어차피 입력되는 문자열에는 괄호밖에 없으니 열린 괄호는 스택에 저장하고 닫힌 괄호가 보이면 스택의 맨 위 원소와 비교한다. 비교해서 두 괄호가 쌍을 이루면 삭제하는 방식으로 하여 결국에는 스택이 비어있는게 모든 괄호가 짝을 이루고 있음을 의미한다.
My Code
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
string p;
void true_or_false() {
int i;
stack <char> s;
for (i = 0; i < p.size(); i++) {
//열린 괄호
if(p[i]=='('||p[i]=='{'||p[i]=='[')
s.push(p[i]);
//닫힌 괄호
else {
if (s.empty()) {
cout << "NO" << endl;
return;
}
if (p[i] == ')' && s.top() == '(')
s.pop();
else if (p[i] == '}' && s.top() == '{')
s.pop();
else if (p[i] == ']' && s.top() == '[')
s.pop();
}
}
if (s.empty())
cout << "YES" << endl;
else
cout << "NO" << endl;
}
int main() {
int C;
int i;
cin >> C;
for (i = 0; i < C; i++) {
cin >> p;
true_or_false();
}
}Answer Code
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
bool wellMatched(const string& formula) {
const string opening("({["), closing(")}]");
stack <char> openStack;
for (int i = 0; i < formula.size(); i++) {
if (opening.find(formula[i]) != -1)
openStack.push(formula[i]);
else {
if (openStack.empty())
return false;
if (opening.find(openStack.top()) != closing.find(formula[i]))
return false;
openStack.pop();
}
}
return openStack.empty();
}
int main() {
int C;
string a;
cin >> C;
for (int i = 0; i < C; i++) {
cin >> a;
if (wellMatched(a))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}Difference & Faults
find 함수
책의 해제 코드는 열린 괄호와 닫힌 괄호를 따로 문자열에 저장하여 특정 괄호가 나왔을 find함수를 통해 인덱스를 반환하도록한다. 이는 새로운 방법 같아보이면서도 충분히 납득이 가는 풀이이다. 조금 아쉬운건 내가 find라는 함수를 모를 뿐더러 정확한 기능을 알아요 사용할 수 있을 거같다. 앞으로 나올 문자열 문제에도 자주 사용될 거 같다.
순회할 문자가 남아있다
처음 코드를 완성했을 때 런타임에러가 떴다. 그 이유를 생각해보니 열린 괄호보다 닫힌 괄호가 많으면 그 짝이 맞지 않기 때문이다. 그래서 닫힌 괄호가 나왔을 때 스택이 비어있는지 유무를 확인하고 넘어갔더니 해결되었다.
Impressions
나는 열린 괄호와 닫힌 괄호는 string에 저장하여 그 인덱스를 통해 쌍을 찾는 방법이 쉬우면서도 참신하였다. 또 나는 학교에서 주로 c언어를 사용하여 다양한 c++라이브러리를 사용할 기회는 별로 없었다. 그래서 이미 표준 라이브러리로 구현이 된 자료구조들을 보면 너무 신기하다.
Summary
이 문제는 저번 학기 자료구조 수업에서 스택을 배우며 풀어본 문제였다. 약간의 어렴풋한 기억으로 풀 수 있었지만 분명히 얻어갈 게 있는 문제였다.
