[BOJ] 백준 4949번: 균형잡힌 세상 (C++)

 

- 문제 출처 : https://www.acmicpc.net/problem/4949

 

---

1. 생각

이번에도 스택 자료구조를 통해서 문제를 해결할 수 있는, 괄호 문제의 확장판 버젼이다.

저번에 java로 괄호문제를 풀었으니, 이번에는 C++로 새롭게 또 풀어보도록 하겠다.

 

이번 문제는 괄호가 두가지가 나온다.

그리하여, 처음 든 생각은 두가지의 스택을 사용해야하나? 싶었는데,

문제의 조건을 살펴보니, 괄호 사이의 문자열도 균형이 잡혀야한다는 조건이 존재했다.

따라서 ( [ ) ] 처럼 다른 괄호에 의해, 짝지어지는 괄호와 바로 대응되지 않는 케이스는

no인 상태로 주어지므로, 하나의 스택만으로도 모든 판별이 가능했다.

 

단순하게 가장 top 에 있는 괄호가 현재 들어온 괄호의 짝이 안된다면 no!

역시나 문제 자체는 정말 심플하게 주어지는 실버 문제다.

 

2. 난관 & 해결 방법

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

 

 C++에서 처음으로 string 자료형을 써보게 되었다.

역시나 string을 include 해서 사용하면 되는 부분이다.

 

bool flag = false;
std::stack<char> stack;
std::string str;
std::getline(std::cin, str);

 

이번 문제에서의 개인적인 난관이었다.

초기화 과정에서 자꾸 문제가 발생해서 틀렸는데,

그 이유는 문자열을 입력받을 때, std::cin 만을 계속 사용했던 것.

알고보니 단순 cin은 공백문자도 구분자로 여기기에, getline을 사용해야 한 줄을 전부 읽을 수 있었다.

 

그 외에는 no가 나올 상황에 필요한 flag를 boolean 자료형으로 만들어줬고,

이전처럼 stack 자료형을 만들었는데, 이번에는 괄호 자체를 저장하기 위해 char형으로 만들었다.

 

또한 string을 초기화 해두고, 이를 getline의 인자로 넣어 매번 한줄씩 읽어와 넣어줬다.

 

if (str == ".")
    break ;
else {
    for (int i = 0; i < str.length(); i ++){
        if (str[i] == '(' || str[i] == '[')
            stack.push(str[i]);
        else if (!stack.empty() && str[i] == ')'){
            if (stack.top() == '(')
                stack.pop();
            else{
                flag = true;
                break ;
            }
        }
        else if (!stack.empty() && str[i] == ']'){
            if (stack.top() == '[')
                stack.pop();
            else{
                flag = true;
                break ;
            }
        }
        else if (stack.empty() && (str[i] == ')' || str[i] == ']')){
            flag = true;
            break ;
        }
    }
    if (!flag && stack.empty())
        std::cout << "yes" << std::endl;
    else
        std::cout << "no" << std::endl;
}

 

. 이 오면 종료하는 조건을 넣어줬고,

그 이후 코드의 로직을 살펴보면, 입력된 앞괄호는 push 해주고,

스택이 비어있지 않은 상태에서 뒷괄호가 오면 짝이 맞으면 pop(), 안맞으면 flag로 추후에 no를 출력시키도록 했다.

empty()를 검사한 이유는, top()을 사용할 때 스택이 비어있으면 segment fault가 떴기 때문이다!

 

또한, 비어있을 때 뒷괄호가 나오는 케이스들을 따로 빼서 if문으로 걸어뒀는데 지금 보니

애초에 top을 사용하기 전에 empty() 가 true 이면 top을 안쓰는 조건으로 걸어주는게 훨씬 나았을 것 같다.

 

그 후 마지막에 플래그와 empty 조건으로 yes 인지 no 인지 판별하여 출력해줬다.

 

3. 코드 및 결론

[ 전체 코드 ]

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

int main(void){
    while(1){
        bool flag = false;
        std::stack<char> stack;
        std::string str;
        std::getline(std::cin, str);
        if (str == ".")
            break ;
        else {
            for (int i = 0; i < str.length(); i ++){
                if (str[i] == '(' || str[i] == '[')
                    stack.push(str[i]);
                else if (!stack.empty() && str[i] == ')'){
                    if (stack.top() == '(')
                        stack.pop();
                    else{
                        flag = true;
                        break ;
                    }
                }
                else if (!stack.empty() && str[i] == ']'){
                    if (stack.top() == '[')
                        stack.pop();
                    else{
                        flag = true;
                        break ;
                    }
                }
                else if (stack.empty() && (str[i] == ')' || str[i] == ']')){
                    flag = true;
                    break ;
                }
            }
            if (!flag && stack.empty())
                std::cout << "yes" << std::endl;
            else
                std::cout << "no" << std::endl;
        }
    }
    return (0);
}

 

[ 결론 ]

 

리팩토링을 너무 안하다보니 게시물을 작성하면서 깨닫는 부분들이 많다.

급하게 코테 문제를 풀어야 하는 상황이 아니라면 리팩토링도 조금씩 하면서

클린코드를 작성하는 요령과 습관을 들여놔야 할 것 같다.

 

또한, 객체지향 언어를 사용하는 이점을 너무 활용하고 있지 못하므로,

조금 더 언어를 공부하면서 좋은 코드를 짜볼 수 있도록 해야할 것 같다.

 

getline과 같은 처음 써보는 것들은 다음 문제를 풀때 잘 활용해봐야겠다.