[백준 4949번] 균형잡힌 세상

---

문제 화면

문제 링크 : https://www.acmicpc.net/problem/4949

문제 풀이

이 문제는 stack의 자료구조를 적절히 활용하는 문제이다. 한 줄씩 읽는데 줄 사이에 끼어있는 괄호를 발견할 경우 적절히 대응해주면 된다. ‘(‘ 나 ‘[’ 처럼 여는 괄호가 있을 경우 아무생각없이 우선 스택에 넣어주면 된다. 그런데 ‘)’ 나 ‘]’ 를 만난 경우

1. 넣으려고 하는데 stack이 비었다 -> 에러
2. 넣으려고 하는데 스택의 top이 쌍이 안맞다 -> 에러
3. 넣으려고 하는데 스택의 top과 쌍이 맞다 -> pop

해주면 된다. ‘.’ 문자를 통해 입력이 종료된것을 확인하면 마지막으로 스택이 비어있지 않은지 한번 더 확인해주면 된다. 잘 풀었다고 생각했는데 baaaaaaarkingdog 님의 코드를 보니 역시 고수는 다르구나 싶다. 아무리 단순한 알고리즘이어도 무의미한 코드는 안쓰도록 노력해야겠다.

제출 코드

#include <iostream>
#include <string>
#include <stack>

using namespace std;

stack<int> s;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int i, error = 0;
    string line;

    

    while(1) {
        getline(cin, line);
        if(line==".") {
            error = 2;
            break;
        }
        for(i = 0 ; i < line.size() ; i++) {
            if(line[i]=='(' || line[i]=='[') {
                s.push(line[i]);
            }
            else if(line[i]==')') {
                if (s.empty()) {
                    error = 1;
                    break;
                }
                else if(s.top()!='(') {
                    error = 1;
                    break;
                }
                else if(s.top()=='(') {
                    s.pop();
                }
            }
            else if(line[i]==']') {
                if (s.empty()) {
                    error = 1;
                    break;
                }
                else if(s.top()!='[') {
                    error = 1;
                    break;
                }
                else if(s.top()=='[') {
                    s.pop();
                }

            }
        }

        if(error==1) cout << "no" << "\n";
        else if(error==2) ;
        else if(!s.empty()) cout << "no" << "\n";
        else cout << "yes" << "\n";

        error = 0;
        while(!s.empty())s.pop();
        
    } 


    return 0;
}

제출코드(최적화)

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

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(true) {
        string a;
        gitline(cin, a);
        if(a==".") break; // 반복문 열자마자 종료 조건 바로 써주자
        stack<char>s; // 매번 새로 만들어주기 cf) 반복문 밖에서 선언하고 계속 스택 초기화 해줄 필요x
        bool isValid = true; // 매번 새로 만들어주기 cf) 다시 error=0으로 초기화해줄 필요x
        for(auto c:a) { // auto 활용하기
            if(c=='(' || c=='[') s.push(c);
            else if(c==')') {
                if(s.empty() || s.top() != '(') {
                    isValid = false;
                    break;
                }
                s.pop();
            }
            else if(c==']') {
                if(s.empty() || s.top() != ']') {
                    isValid = false;
                    break;
                }
                s.pop();
            }           
            if(!s.empty()) isValid = false;
            if(isValid) cout << "yes\n";
            else cout << "no\n";
        }
    }
}

결론

쉬운 문제부터 코드를 최적화 하는 연습을 하자.

출처

• https://blog.encrypted.gg/936?category=773649