[백준] 4949번 문제 풀이

www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

간략 풀이 : 

1. getline함수를 이용해서 공백을 포함한 문자열을 입력받음

2. 맨 처음에 해당 문자열이 '.' 한 개의 점으로만 이루어져 있는지 검사후에 종료

3. 입력받은 문자열의 길이만큼 반복문을 돌면서 각각 괄호끼리 짝이 맞는지 검사를 하는데 이 부분이 조금 복잡할 수도 있음

4. 괄호의 짝이 맞는지 검사를 하면서 초기화 한 플래그 변수를 이용해서 출력

풀이 : 

먼저 주어지는 문자열로 '.'만 입력이 된다면 바로 종료한다는 의미로 다음과 같은 코드를 사용했다.

getline함수를 사용한 이유는 일반적인 cin >> string을 이용하면 공백을 포함한 문자열을 입력받지 못하기 때문에 사용했다.

string s;
while(true){
    //...
    getline(cin, s);
    if(s == ".") break;
    //...
}

그리고 입력받은 문자열 중에서 괄호의 짝을 찾으려면 문자열의 길이만큼 반복문을 돌면 충분히 해결할 수 있을 것 같아서 문자열의 길이만큼 반복문을 돌리기로 결정한 코드는 다음과 같다.

while(true){
    //...
    for(int i = 0; i < s.length(); i++){
        //...
    }
    //...
}

반복문을 돌면서 해결해야 할 가장 큰 문제는 어떻게 괄호의 짝을 찾는지에 대한 것이다.

그렇다면 무분별하게 흩어져 있는 괄호를 어떤 규칙을 통해서 찾아야 하는 것일까?

규칙을 찾기 가장 쉬운 예를 들어보자. 아래는 문제의 예제 입력 중 하나의 케이스를 가져온 것.

([ (([( [ ] ) ( ) (( ))] )) ]).

이 문자열에서 어떻게 괄호의 짝이 일치하는지 또 어긋나지는 않았는지를 확인할 수 있을까?

먼저 맨 처음에는 ')'가 나오면 절대 괄호의 짝은 찾을 수 없다. 그 이유는 맨 처음에 닫은 괄호가 나와버리면 나중에 열린괄호가 나왔다 하더라도 닫은 괄호가 먼저 나와버렸기 때문에 절대 짝을 찾을 수 없다. (이건 금방 이해를 할 수 있을 것이다.)

그렇다면 어느 시점에 열린 괄호가 먼저 나온 뒤에 닫은 괄호가 나온다면? 어떻게 효율적으로 확인할 수 있을까?

그 효율적으로 확인할 수 있는지에 대한 방법을 생각하는 것이(내가 생각하기에는) 이 문제를 해결하기 위한 가장 중요한 해결책이다.

바로 스택을 사용하는 것이다. 문제의 하단에 알고리즘 분료를 보면 스택이 항목에 포함되어 있다.

스택을 사용해서 열린 괄호를 차곡 차곡 쌓아둔 뒤에 나중에 닫힌 괄호가 나오게 되면(즉 괄호의 짝이 맞는다면) 스택에 들어있던 열린 괄호를 삭제하는 방식으로 문제를 풀어나가면 된다.

 

전체 코드 : 

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
    string s;
    while (true) {
        getline(cin, s);
        if (s == ".") break;
        stack<char> s_str;
        bool res = false;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ')') {
                // 이 부분은 내가 짠 코드가 아님
                // 더 효율적인 코드가 있길래 그걸로 변경
                if (s_str.empty() || s_str.top() != '(') {
                    res = true;
                    break;
                }
                s_str.pop();
            }
            else if (s[i] == ']') {
                if (s_str.empty() || s_str.top() != '[') {
                    res = true;
                    break;
                }
                s_str.pop();
            }
            else if (s[i] == '(' || s[i] == '[') {
                s_str.push(s[i]);
            }
        }
        // res가 true이거나 s_str 스택이 비어있지 않으면 땡
        if (res || !s_str.empty()) cout << "no\n";
        else cout << "yes\n";
    }
}