상세 컨텐츠

본문 제목

[C++] 백준 4949번 : 균형잡힌 세상 && stream flag

카테고리 없음

by 별달하현 2023. 7. 27. 18:40

본문

- 문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

  • 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
  • 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
  • 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
  • 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
  • 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

 

- 입력

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

입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

 

- 출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

 

- 예제

//INPUT//
//OUTPUT//
So when I die (the [first] I will see in (heaven) is a score list).
yes
[ first in ] ( first out ).
yes
Half Moon tonight (At least it is better than no Moon at all].
no
A rope may form )( a trail in a maze.
no
Help( I[m being held prisoner in a fortune cookie factory)].
no
([ (([( [ ] ) ( ) (( ))] )) ]).
yes
 .
 yes
.

 

 

 

 

- 구상

백준 사이트의 문제 단계별 풀기 부분의 '스택' 카테고리를 보면, 이 문제의 바로 전 문제가 더 간단한 것을 볼 수 있다. 지금은

  1. 괄호의 종류가 두 개가 생겼으니, 이를 구분하는 방법을 구현해야한다.
  2. 입력되는 텍스트의 개수를 정해주지 않았기에, 마침표(.)를 기준으로 문장을 나누고, 마침표가 하나만 찍혔을 때, 프로그램을 종료하는 구조를 짜야한다.

➡ 1번의 경우, 스택의 특징을 조금 더 이용해보면 된다. top()함수를 이용할 것이다.

 

➡ ( [ ) 와 같은 상태가 문제가 되는 것이기에, 다음과 같은 bool type 함수를 만들어줄 것이다.

  1. 왼쪽 괄호( ( , [ )가 입력된다면 스택을 생성하여, 얌전히 넣어주고, 오른쪽 괄호( ) , ] )가 그 뒤에 알맞게 입력된다면, 스택에 pop()함수를 시행하여, 스택 내에 괄호를 사라지게 해준다.
  2. 오른쪽 괄호( ) , ] )가 스택이 빈 상태(empty()함수의 return값이 1일 때)에 입력받는다면, 혹은 스택의 최상단(top()함수의 return값)과 현재 검출된 괄호의 종류가 다르다면(소괄호, 대괄호 구분), 바로 false를 return한다.
  3. 1,2번에 맞게 반복문을 수행후, 스택이 비어있다면 → 괄호가 알맞게 처리된 상태라면, true를 return.
  4. 1,2번에 맞게 반복문을 수행후, 스택이 비어있지 않다면 → 괄호가 알맞게 처리되지 못한 상태라면, false를 return.

 

➡ 2번의 경우, stream flag라는 개념을 사용할 것이다.

 

➡ C++는 stream이라는 개념이 있다. 이는 연속적인 데이터의 흐름 혹은 데이터를 전송하는 소프트웨어 모듈을 말한다. 객체를 입출력하는 과정에서 콘솔이나 파일의 입출력을 직접 다루지 않고, 출력을 원하면 출력 스트림에, 입력을 원하면 입력 스트림에 넣어서 입출력을 시행한다.

 

➡ 이런 stream에는 flag라는 개념이 있는데, flag란 간단히 말해서, 입출력 과정에서 주어진 value를 어떻게 표현할 지 등을 정해줄 수 있는 것이다.

 

➡ 이는 위 그림과 같이, flag를 on 하고 싶다면, setf()를, off하고 싶다면 unsetf()을 취하면 된다.

setf(ios::flag name);   	//ON
unsetf(ios::flag name);      //OFF

 

➡ 이번 문제에서 사용할 flag는 skipws로 쉽게 말해, spacebar와 enter로 생기는 공백도 입력값에 넣어주는 역할을 한다. 이는 defalut값이 on으로 설정되어 있다.

 

➡ 일반적은 입력과정에서, string을 입력받는다고 할 때, spacebar와 enter는 문자열을 끊어주는 역할을 한다. 그러니,

std::string str;
std::cin >> str;

//INPUT//
I am happy

//what's in str for real//
str == I

다음과 같은 사태가 발생하는 것이다.

 

➡ 그래서 만약 unsetf()를 사용하게 되고, 마침표를 기준으로 입력받는 값을 while()문 등에서 탈출시킨다고 하면, 

std::string str="";
cin.usnetf(ios::skipws);
std::cin >> str;

//INPUT//
I am happy.

//what's in str for real//
str == I am happy

와 같이 만들 수 있는 것이다.

 

➡ 이때 탈출 조건 형성이 중요한데, 이것땜에 푸는 데에 좀 오래걸렸다 문자열을 계속 입력 받다가, 마침표를 제외한 문장만 검출하기에 그리고 문자열에 마침표만 온다고 해서, str의 값이 변하지 않았음을 기준으로 하면 문제다.

 

➡ skipws가 off된 상태이기에, 다음 문자열로 넘어오면서 받는 enter의 값인 \n값이 str에 들어가게 되는 것이다. 그래서 반복문 탈출조건은 str에 \n만 있을 때로 정해야한다.

 

 

 

 

 

- 구현

꽤 절망적이게도, 생각한 시간이 무색하게, 더 2번의 해법으로 더 쉬운 방법이 있다. getline()함수를 사용하면 된다.

getline()이란, 줄(line) 단위로 string data를 입력받는 방법이다.

구현 방법은 string str; getline(사용하는 stream, str); 이다. 이 경우에선 getline(cin, str);이라고 하면 된다.

이 방법이면, 위에서 사용한 flag 없이, 문제를 해결할 수도 있다.

더 간단한 방법을 찾았으니, 오히려 좋다. 이제 구현해보자.

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool is_VPS(const string& s){
  stack<char> check_list;

  for(int i=0;i<s.size();i++){
    if(s[i]=='(')
      check_list.push('(');

    else if(s[i]==')'){
      if(check_list.empty())
        return false;
      if(check_list.top()=='['){
        return false;
      }

      check_list.pop();
    }
    else if(s[i]=='[')
      check_list.push('[');

    else if(s[i]==']'){
      if(check_list.empty())
        return false;

      if(check_list.top()=='('){
        return false;
      }

      check_list.pop();
    }
  }
  if(check_list.empty())
    return true;
  else
    return false;
}


int main() {

	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    //구현 단계에서 한 getline()을 이용한 방법
  /*
  while(1){
  	string str="", str_total;
    getline(cin, str); //str에 입력받은 줄이 들어간 것이다.
    
    if(str[0]=='.')
    	break;
        
    if(is_VPS(str))
      cout<<"yes"<<endl;

    else
      cout<<"no"<<endl;
  }
  */
	
  //구상단계에서 한 flag를 통해 하는 방법
  char s;
  
  cin.unsetf(ios::skipws);
  while(1){
    string str="";
    while(cin>>s){
      if(s!='.')
       str+=s;
      else
       break;
    }

    if(str=="\n")
      break;

    if(is_VPS(str))
      cout<<"yes"<<endl;

    else
      cout<<"no"<<endl;
  }
  
  
	return 0;
}

 

티스토리툴바