백준 4949번 C++ 풀이

https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

시간 제한	메모리 제한	solved.ac 티어
1초	128MB	실버 4

 

 

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

---

https://codejin.tistory.com/80

백준 9012번 C / C++ 풀이

 

이 문제의 연장문제. 소괄호로만 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를 출력한다.

 

실행결과