[알고리즘] 4949번: 균형잡힌 세상

0. 문제

 

4949번: 균형잡힌 세상

 

---

1. 문제 이해

 

1. 문자열을 입력받는다.
2. .이면 프로그램을 종료한다.
3. 각 문자열마다 (, [는 스택에 push한다.
4. 스택이 언더플로우가 아니라면 ), ]는 pop한다.
5. 스택 언더플로우라면 no를 출력한다.
6. 스택에 (, ]이 남아있다면 no를 출력한다.
7. 스택이 비어있다면 yes를 출력한다.

 

---

2. 제출

 

가. 틀렸습니다.

// 백준 4949번: 균형잡힌 세상
#include <iostream>
#include <string>
#include <stack>
#include <vector>
using namespace std;

const string delimeter = ".";
string input="", str="";

bool check(string str){
  stack<char> stk;
  for(char c : str){
    if(c == '(' || c == '[')stk.push(c);
    if(c == ')'){
      if(stk.size() && stk.top() == '('){
        stk.pop();
      }else{
        return false;
      }
    }
    if(c == ']'){
      if(stk.size() && stk.top() == '['){
        stk.pop();
      }else{
        return false;
      }
    }
  }
  return stk.empty();
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);

  while(cin >> input){
    str+=input;
        if(str==".")break;
    auto pos = str.find(".");
    bool endOfLine = (pos != string::npos);
    if(endOfLine){
      if(check(str)) cout << "yes\n";
      else cout << "no\n";
      str = "";
    }
  }

  return 0;
}

1. 입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.
2. " ."와 같이 괄호가 하나도 없는 경우도 균형 잡힌 문자열로 간주할 수 있다.

 

위 두 조건을 모두 만족하기 위해선 “.”와 “ .”를 구분할 줄 알아야 한다.

 

일반적인 cin는 공백문자를 인식하지 못하기 때문에 일반적인 cin이 아닌 다른 방식으로 공백문자까지도 입력을 받아야 한다.

 

---

나. 수정

// 백준 4949번: 균형잡힌 세상
#include <iostream>
#include <stack>
using namespace std;

string str="";

bool check(string str){
  stack<char> stk;
  for(char c : str){
    if(c == '(' || c == '[')stk.push(c);
    if(c == ')'){
      if(stk.size() && stk.top() == '('){
        stk.pop();
      }else{
        return false;
      }
    }
    if(c == ']'){
      if(stk.size() && stk.top() == '['){
        stk.pop();
      }else{
        return false;
      }
    }
  }
  return stk.empty();
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);

  while(getline(cin, str)){
    if(str==".")break;
    if(check(str)) cout << "yes\n";
    else cout << "no\n";
  }

  return 0;
}

• while(getline(cin, str)){…} : getline()을 사용하여 한 문장을 입력으로 받았다. 이렇게 하면 공백문자도 입력받을 수 있다.
• if(str==".")break; : "."을 입력받으면 종료한다.
• if(stk.size() && stk.top() == '('){ : 스택의 top을 사용하기 전에는 반드시 스택의 사이즈를 확인한다. (언더플로우 예방)

 

---