이번에는 백준 4949번 균형잡힌 세상 문제를 풀어보았습니다.
이 문제는 문자열 안에 있는 소괄호 ()와 대괄호 []가 균형을 이루고 있는지를 판단하는 문제입니다.
괄호 종류가 두 가지로 늘어났지만, 핵심은 여전히 여는 괄호와 닫는 괄호의 짝을 올바르게 맞추는 것이었고, 그래서 이번에도 stack 자료구조를 사용했습니다.
문제 설명
문자열에는 영문 알파벳, 공백, 소괄호, 대괄호가 들어올 수 있습니다.
이 중 괄호들이 균형을 이루는지 판단해야 합니다.
균형을 이루려면 다음 조건이 만족되어야 합니다.
- 모든
(는)와 짝을 이루어야 한다. - 모든
[는]와 짝을 이루어야 한다. - 닫는 괄호가 나왔을 때, 그와 짝이 되는 여는 괄호가 앞에 있어야 한다.
- 괄호의 짝 순서도 올바르게 맞아야 한다.
입력은 여러 줄로 주어지고,
한 줄이 "." 하나만 들어오면 입력이 종료됩니다.
각 줄에 대해 균형이 맞으면 "yes", 아니면 "no"를 출력하면 됩니다.
풀이 아이디어
이 문제는 (), [] 두 종류의 괄호 쌍을 찾아야 하기 때문에 stack을 사용했습니다.
기본 흐름은 다음과 같습니다.
(또는[가 들어오면 stack에 push)가 들어오면 stack top이(인지 확인]가 들어오면 stack top이[인지 확인
즉, 닫는 괄호가 나왔을 때 현재 가장 최근의 여는 괄호와 종류까지 맞아야 한다는 점이 중요했습니다.
그리고 문자열을 끝까지 다 본 뒤에도 stack이 비어 있지 않다면,
짝이 맞지 않은 여는 괄호가 남아 있다는 뜻이므로 균형이 맞지 않은 문자열입니다.
V1 코드
#include <bits/stdc++.h>
using namespace std;
bool check(string s) {
stack<char> stk;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(' || s[i] == '[')
stk.push(s[i]);
else if (s[i] == ')') {
if (stk.empty() || stk.top() != '(')
return false;
stk.pop();
} else if (s[i] == ']') {
if (stk.empty() || stk.top() != '[')
return false;
stk.pop();
}
}
return stk.empty();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string s;
vector<bool> ret;
while(getline(cin, s)) {
if (s == ".")
break;
ret.push_back(check(s));
}
for (int i = 0; i < ret.size(); i++) {
if (ret[i])
cout << "yes\n";
else
cout << "no\n";
}
}풀이 흐름
- 한 줄씩 문자열을 입력받는다.
- 입력이
"."이면 종료한다. - 문자열을 앞에서부터 한 글자씩 확인한다.
- 여는 괄호
(또는[이면 stack에 push 한다. - 닫는 괄호
)또는]이면 stack이 비어 있는지, top이 올바른 괄호인지 확인한다. - 조건이 맞지 않으면 바로 false를 반환한다.
- 문자열을 끝까지 확인한 뒤 stack이 비어 있으면 true, 아니면 false를 반환한다.
- 결과를
"yes"또는"no"로 출력한다.
구현 포인트
1. 두 종류의 괄호를 모두 stack으로 관리
이번 문제는 소괄호와 대괄호 두 종류를 모두 처리해야 합니다.
그래서 여는 괄호가 나오면 종류에 관계없이 stack에 넣고,
if (s[i] == '(' || s[i] == '[')
stk.push(s[i]);닫는 괄호가 나왔을 때 그에 맞는 여는 괄호가 stack top에 있는지를 확인했습니다.
즉, 단순히 개수만 맞는 것이 아니라 종류와 순서까지 맞아야 한다는 점이 중요했습니다.
2. ) 가 왔을 때는 ( 와 짝인지 확인
닫는 소괄호 ) 가 들어왔을 때는 두 가지를 검사해야 합니다.
- stack이 비어 있지 않은지
- stack top이
(인지
else if (s[i] == ')') {
if (stk.empty() || stk.top() != '(')
return false;
stk.pop();
}즉, 앞에 짝이 될 여는 소괄호가 없거나, 다른 종류의 괄호가 위에 있으면 바로 균형이 맞지 않는 문자열입니다.
3. ] 가 왔을 때는 [ 와 짝인지 확인
닫는 대괄호 ] 도 같은 방식으로 검사했습니다.
else if (s[i] == ']') {
if (stk.empty() || stk.top() != '[')
return false;
stk.pop();
}이렇게 해서 괄호의 종류가 뒤섞여 잘못 매칭되는 경우도 걸러낼 수 있습니다.
예를 들어 ([)] 같은 경우는 개수만 보면 맞아 보이지만, 순서가 틀렸기 때문에 false가 됩니다.
4. 문자열이 끝난 뒤 stack이 비어 있어야 함
중간에 문제 없이 끝까지 왔다 하더라도, stack 안에 여는 괄호가 남아 있다면 균형이 맞지 않습니다.
이 코드는 마지막에
return stk.empty();로 처리했습니다.
즉,
- stack이 비어 있으면 균형이 맞는 문자열
- 비어 있지 않으면 짝이 남은 문자열
로 판단할 수 있습니다.
5. 이번 문제에서는 getline 사용
이 문제는 문자열 안에 공백도 들어올 수 있기 때문에 cin >> s 가 아니라 getline(cin, s)를 사용했습니다.
while(getline(cin, s)) {이 부분이 중요합니다.
공백이 있는 입력을 한 줄 전체로 받아야 하기 때문입니다.
그리고 입력 종료 조건이 "." 한 줄이기 때문에, 그것도 문자열 전체 비교로 처리했습니다.
if (s == ".")
break;