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

4949번 균형잡힌세상

위 문제는 단계별 문제 중 스택 문제에 해당하는 문제이다. 백준에서 스택 단계에서 만날 수 있는 문제이며, 괄호 짝을 확인하는 전형적인 “스택” 문제라고 생각하면 쉽다.

현재 업무에서 C++을 언어를 주 언어로 하다보니, C++로 모든 것을 연습하고자한다. 따라서 이번 문제도 C++를 보고 풀었으나, 다른 사람들이 푼 소스코드를 보거나, 지식이 부족한 부분에 대해 추가적으로 정리하고자 한다.

문제

균형잡힌세상는 주어진 조건을 만족할 경우 Yes or No로 판별한 결과를 출력하는 문제이다.

아래의 조건을 만족하면 Yes 아니면 No를 출력하면 된다.

문제 풀이

위의 균형잡히기 위한 조건을 보자. “[” , “(“ 각각 짝을 이뤄야하며, 1:1 매칭이 가능해야하고 순서도 맞아야한다 (“[” 와 “)” 가 만날 경우 틀림). 순서에 따른 괄호의 짝을 어떻게 판별할까? 나는 LIFO 구조로 문제를 접근해 풀었다. 1. “.” 이 들어올 경우 종료 2. stack push의 기준 2.1. “[”, “(“ 가 들어올 경우 push해 데이터 저장 2.2. “]”, “)” 경우 pop을 통해 “[” , “(“ 가 짝을 이루는지 판단 맞으면 skip 틀릴경우 break (시간 끌 필요 없이 바로 No 판단). 2.3. 다른 문자는 skip 3. puts로 현재 stack이 empty가 아닐경우 괄호가 짝이 맞지 않은 것이니 No, 아닐 경우 Yes로 판단

위의 로직을 통해 문제를 풀었다.

예를들어, [(haha)] 있을 경우를 생각해보자.

• ”[”, “(“ push
• “haha” skip
• ”)” 경우 pop을 통해 “(“ 맞는지 판단. 맞을 경우 다음 글자 입력받음
• ”]” 경우 pop을 통해 “]” 맞는지 판단.
• stack == empty.
  • 따라서, 괄호의 짝을 다 맞췄기 때문에 균형잡힌 세상으로 판단

#include <iostream>
#include <stack>
using namespace std;
int main()
{
  while(1)
  {
    stack<char> st;
    string str;
    getline(cin, str);
    if (str[0] == '.') break;
    for (int i = 0; i < str.length(); i++) {
      if (str[i] == '[' || str[i] == '(') {
        st.push(str[i]);
        continue;
      }
      if (str[i] == ']' || str[i] == ')') {
        if (st.empty()) {
          st.push('.');
          break;
        }
        if (str[i] == ']') {
          if (st.top() != '[') break;
          st.pop();
        } else if (str[i] == ')') {
          if (st.top() != '(') break;
          st.pop();
        }
      }
    }
    puts(!st.empty() ? "no" : "yes");
  }
}

C++ 에서 standard library인 stack을 사용하기 위해서는 stack header file이 필요하다. 위에서 재밌게 볼 수 있는 점은 puts를 사용했다는 점이다. 이전 posting에서 다른 사람이 puts를 활용하는 것을 봤으며 적용해 풀어보았다.

소스코드를 깔끔히 작성하지 못했던 점이 존재한다. 다만, 현재는 초보이니 구현력에 초점을 맞추고 블로그 포스팅을 하도록 한다.

생각하지 못한 부분

문제를 풀 때, 단번에 통과를 하지 못했다. 3가지 정도 잘못 접근한 부분이 있어 정리하고자한다.

• getline 입력
• 공백 문자를 포함한 문자열을 입력 받기 위해서는 cin이 아닌 getline 함수를 써야한다. 여기서 말하는 공백문자란 개행문자 혹은 띄워쓰기를 말한다.

• getline 같은 경우 다룰 이야기가 많아 여기를 클릭해서 확인해보기 바란다.

• stack empty 체크
  • Runtime 에러가 발생을 했다. segmentation fault가 발생하며, runtime error가 출력됐는데 확인해 본 결과 index를 잘못 참조해서 발생하는 거라고 했다.
  • stack 내 값이 존재하지 않을 경우 즉, empty일 때 top()를 통해 요소에 접근하고자 한다면 영역을 벗어나 segmentation fault 함수가 발생한다.

• push 하는 부분 예외

    while(1)
  {
    stack<char> st;
    string str;
    getline(cin, str);
    if (str[0] == '.') break;
    for (int i = 0; i < str.length(); i++) {
      if (str[i] == '[' || str[i] == '(') {
        st.push(str[i]);
        continue;
      }
      if (!st.empty()) {
        if (str[i] == ']') {
          if (st.top() != '[') break;
          st.pop();
        } else if (str[i] == ')') {
          if (st.top() != '(') break;
          st.pop();
        }
      }
    }
    puts(!st.empty() ? "no" : "yes");
  }
  

위 소스코드는 왜 틀렸다고 나오는 것일까? “예시는 다 동작한다.” 확인해 본 결과, “[”, “(“ 대해 push를 통해 stack에 넣는다. 다만, “(“, “[” 케이스가 아닐 경우 고려하지 않아 나머지 문자들은 skip된다. 만약 “)” , “]” 하나만 들어올 경우 어떻게 처리될 것인가. 바로 yes라고 판별한다. 즉, ”]” , “)” 예외에 대한 고려를 하지 않는 것이 문제 인것이다. 이를 해결하기 위해서는 예외를 처리하도록 if이 필요하다. 최종 소스는 위에 풀이 소스를 확인해보자.

Reference

• 백준 질문 검색