https://www.acmicpc.net/problem/4949
시간 제한 | 메모리 제한 | solved.ac 티어 |
1초 | 128MB | 실버 4 |
문제
세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.
정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
- 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
- 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
- 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
- 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
- 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.
입력
하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.
출력
각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.
https://codejin.tistory.com/80
이 문제의 연장문제. 소괄호로만 vps를 따지던 문제에서 소괄호와 대괄호가 섞인 문제이다. 방법은 9012번과 유사하다.
일단, 문자열을 다루기 편하게 하고자, 들어온 문자열에서 괄호만 남도록 문자열을 적절히 바꿔줬다(change_to_ps 함수).
열리는 괄호가 들어올때마다 push하고, 닫히는 괄호가 들어올때, top과 비교하여 쌍이 맞으면 pop하고,아니라면 그냥 push한다.
최종적으로 스택에 무언가가 남아있다면, 조건에 맞지 않기 때문에 no, 비어있다면 yes를 출력한다.
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
string change_to_ps(string& str){
string result = "";
for(char& x : str) {
if(!isalpha(x) && !isblank(x) && x != '.') result += x;
}
return result;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string line;
while(true) {
stack<char> st;
getline(cin, line);
if (line == ".") break;
line = change_to_ps(line);
// ")string(" 이나 "]string["같은 문자열인지 사전에 미리 검사
if(*line.begin() == ')' || *line.begin() == ']' || *(line.end() - 1) == '(' || *(line.end() - 1) == '['){
cout << "no" << endl;
continue;
}
else {
for(const char& x : line) {
if (x == '(' || x == '[') st.push(x);
else if(x == ')'){
if (!st.empty() && st.top() == '(') st.pop();
else st.push(x);
}
else if(x == ']'){
if (!st.empty() && st.top() == '[') st.pop();
else st.push(x);
}
}
}
if (st.empty()) cout << "yes" << endl;
else cout << "no" << endl;
}
}
쉽게 이해가 가지 않을 수 있기 때문에, 예제에서 yes가 나오는 예제와 no가 나오는 예제를 하나씩 살펴보자. 백준 예제에 나온 1번(So when I die (the [first] I will see in (heaven) is a score list).) 예제와 5번(Help( I[m being held prisoner in a fortune cookie factory)].) 예제를 살펴보자.
1번 예제인 "So when I die (the [first] I will see in (heaven) is a score list)." 가 change_to_ps 함수를 거치면 "([]())" 가 될 것이다.
이제 스택을 선언하고 여는 괄호인 "(["까지 push하면, 다음과 같이 될 것이다.
1번 예제 스택 | ( | [ |
여기서 다음 괄호인 "]" 가 들어온다. 스택의 top이 "[" 이기 때문에, pop을 수행한다.
1번 예제 스택 | ( |
이후, "()" 가 차례로 push, pop이 된다. 그리고 맨 마지막으로 ")" 가 들어오고, top이 "(" 이기 때문에, pop이 수행되면서, 끝난다. 이때의 스택은 다음과 같다.
1번 예제 스택 |
스택이 비어있는 것을 알 수 있다. 비어있기 때문에 이 예제는 균형을 이루고 있다. 즉, yes를 출력한다.
이제 5번 예제인 "Help( I[m being held prisoner in a fortune cookie factory)]." 를 살펴보자. 역시 change_to_ps 함수를 거치면, "([)]" 이 된다. "([" 까지는 여는 괄호이기 때문에, 스택에 push한다.
5번 예제 스택 | ( | [ |
이때, ")" 가 들어온다. 스택의 top은 "[" 이므로, 그냥 push한다.
5번 예제 스택 | ( | [ | ) |
마지막으로 들어오는 "]" 의 경우도, top이 "(" 이기 때문에 역시 push한다. 실행이 끝나고, 스택을 살펴보면, 다음과 같다.
5번 예제 스택 | ( | [ | ) | ] |
스택이 비어있지 않기 때문에, 이 예제는 균형을 이루지 않는다. 즉, no를 출력한다.
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 1783번 C++ 풀이 (0) | 2022.03.07 |
---|---|
백준 1080번 C++ 풀이 (0) | 2022.03.07 |
백준 9659번 C++ 풀이 (0) | 2022.02.16 |
백준 1874번 C++ 풀이 (0) | 2022.02.13 |
백준 20364번 C++ 풀이 (0) | 2022.02.06 |