Back to Blog
알고리즘스택괄호자료구조

0x08. 스택의 활용 - 수식의 괄호 쌍

스택을 활용한 괄호 쌍 검사 문제 해결 방법을 정리한다.

0x08 스택의 활용 (수식의 괄호 쌍)

0x01 문제 해결을 위한 관찰

괄호 종류가 하나면 닫는 괄호")"의 수가 여는 괄호"("의 수를 넘으면 안되는 것으로 판단이 가능 -> 하지만 종류가 여러가지

"문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각해도 된다."

0x02 문제 해결 방법

  1. 여는 괄호가 나오면 스택에 추가.
  2. 닫는 괄호가 나왔을 경우, 2-1 스택이 비어있으면 올바르지 않은 괄호 쌍 2-2 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍 2-3 스택의 top이 짝이 맞는 괄호일 경우 pop
  3. 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍, 남아있지 않으면 올바른 괄호 쌍

0x03 연습문제

BOJ 4949 : 균형잡힌 세상

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s;
    while(1) {
        stack<char> S;
        getline(cin, s);
        if(s == ".") break;

        bool check = true;
        for(char c : s) {
            if(c == '(' || c == '[') {
                S.push(c);
            }
            else if(c == ')' || c == ']') {
                if(S.empty()) {
                    check = false;
                    break;
                }
                else if(c == ')' && S.top() == '(') S.pop();
                else if(c == ']' && S.top() == '[') S.pop();
                else {
                    check = false;
                    break;
                }
            }
        }

        if(!S.empty() || !check) cout << "no\n";
        else cout << "yes\n";
    }
}

BOJ 10799 : 쇠막대기

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    stack<char> S;
    string s;

    cin >> s;
    int count = 0;
    for(int i=0; i<s.size(); i++) {
        if(s[i]= '(' && s[i+1] = ')') {
            count ++;
            S.push(s[i]);
        } else if(s[i]= '(' && s[i+1]= ')') {
            count = S.size();
            i++;
        } else S.pop();
    }
    cout << count << "\n";
}

문제 풀이

이번 강의에 해당하는 문제는 총 5개였다.

연습문제는와 응용문제 2개는 강의를 들으면서 잠시 멈춰놓고 해결하였고, 끝난 후에 기본문제 2개를 마저 풀어보았다.

Note_ 2504 괄호의 값 : 이 문제가 좀 어려웠다. 스택에 괄호를 저장하면서 괄호안에 괄호가 있으면 데이터를 저장해두었다가 곱해서 더해야하는게 생각이 나지 않아서 많이 헤맸다. 고민 끝에 답안을 보게 되었고 따로 변수하나를 선언해서 곱하기를 해두어서 저장해두고 전 인덱스가 여는 괄호면 데이터를 더하는 식으로 해결하는 것을 알 수 있었다.

3986 좋은 단어 : 쉬운 문제를 너무 어렵게 생각하였다. 괄호가 아니라서 열고 닫는 구분이 없다보니 그냥 top에 같은 값이 있으면 pop, 아니면 push해서 empty인지 확인하면 끝이였다.

리뷰

스택의 활용, 간단한 괄호문제는 정말 간단하였지만 응용문제를 보니 정말 많은 것을 생각해야해서 머리가 정리에서 안됐다.

역시 아직 갈길이 멀었다.

방학 끝나기 전에 마무리하려면 좀 더 열심히 해야겠다 ,,

다음은 0x09강 BFS으로 돌아오겠다.

출처: 바킹독님의 실전알고리즘 강의

PS 시리즈26편