백준 문제풀이/백준 Silver

백준 4949 - 균형잡힌 세상 [C/C++]

LKBaekjoon 2023. 11. 2. 16:00
반응형

4949번: 균형잡힌 세상 (acmicpc.net)

 

4949번: 균형잡힌 세상

각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에

www.acmicpc.net

문제 설명은 다음과 같다.

문제 설명 / 입력 / 출력
예제 입력 / 예제 출력

백준 9012 - 괄호 [C/C++ :: 대학원생의 백준 / 딥러닝 저장소 (tistory.com)

 

백준 9012 - 괄호 [C/C++

9012번: 괄호 (acmicpc.net) 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올

baekjoon-deeplearning.tistory.com

전에 썼던 나의 포스팅에서 언급했듯이, 괄호 문제를 푸는 알고리즘은 거의 정해져 있다.

 

열린 괄호들이면 스택에 다 넣어놨다가, 닫힌 괄호가 나올 때마다 pop 시키는 것이다.

 

비어 있으면 닫힌 괄호의 수가 많으니 no 이고,

다 pop 시키고도 아직 스택에 열린 괄호가 남아 있다면, 짝이 역시나 맞지 않으니 no를 뱉으면 된다.

 

이 문제는 허나 소괄호와 대괄호를 다 가지고 있으니, 그걸 구분해 주는 코드 한줄만 조건문에 넣어서 분기시켜주면 될 것이다.

 

아래는 제출한 코드이다.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string test;
    vector<char> opened;

    while (getline(cin, test)) {
        if (test==".") {
            break;
        }
        else {
            opened.clear();
            int m =0;
            for (int i=0;i<test.length();i++){
                if (test[i]=='(' || test[i]=='[') opened.push_back(test[i]);
                else{
                    if (test[i]==')'){
                        if (opened.back() =='(' && !opened.empty()) opened.pop_back();
                        else {
                            m=1;
                            break;
                        }
                    }
                    else if (test[i]==']'){
                        if (opened.back()=='[' && !opened.empty()) opened.pop_back();
                        else {
                            m=1;
                            break;
                        }
                    }
                }
            }
            if (opened.empty() && m==0) cout << "yes" << '\n';
            else cout << "no" << '\n';
        }
    }
    return 0;
}

 

opened 라는 Vector를 선언해서, 열린 괄호가 나올 때마다 넣어 주었고, 뺄 때는 뒤에서부터 빼야 하니 (First in Last Out) 벡터 자료구조가 안성맞춤이었다.

 

닫힌 괄호가 나올 때마다 opened 벡터에서 pop_back 시킨 결괏값이 대괄호 소괄호 짝은 맞는지를 비교해주는 코드를 작성해서 분기를 나누었다.

반응형