BOJ 4949 (S4) 균형잡힌 세상

문제 요약

소괄호( ), 대괄호[ ]의 짝이 잘 지어져 있는 올바른 문장인지 확인해보자. 괄호가 없는 경우에도 올바른 문장으로 판단한다.
(단, 모든 문장은 온점.으로 종료되고, 마지막 입력은 .만을 받는다.)

풀이 방향

문장의 내용과 관계 없이, 괄호가 올바르게 열고 닫아지는지 확인하면 된다. 괄호는 나열되거나 안길 수 있다.

//괄호가 올바르게 열고 닫아진 경우
"( ) [ ]"
"( [ ] ) ( )"

//괄호가 올바르지 않게 사용된 경우
"( [ ) ] [ )"
"] ) ( )"

올바르지 않은 예시를 자세히 보면, 세 가지 특징을 확인할 수 있다.
1. 마지막으로 열린 괄호와 처음으로 닫힌 괄호의 짝이 맞지 않는 경우
2. 열린 괄호 없이 닫힌 괄호가 최초로 등장하는 경우
3. 열린 괄호와 닫힌 괄호의 개수가 다른 경우

즉, 괄호는 언제든지 열 수 있지만 닫을 때는 주의가 필요하며, 마지막으로 열린 괄호가 어떤 형태인지(혹은 없는지) 확인이 필요하다.

후입선출(LIFO)의 성격을 갖는 stack을 적절하게 사용해 보자.
특히 stack.top();을 활용하여 이 문제를 해결해 보자.

제출 답안

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

int main() {
    while(1) {
        string str;
        getline(cin, str);
        if(str[0]=='.')
            break;
          
        stack<int> st;
        for(int i=0; i<str.size(); i++) {
            if(str[i]=='(') {
                st.push(1);
            }
            else if(str[i]==')') {
                if(!st.empty() && st.top()==1)
                    st.pop();
                else {
                    st.push(0);
                    break;
                } 
            } else if(str[i]=='[') {
                st.push(2);
            } else if(str[i]==']') {
                if(!st.empty() && st.top()==2)
                    st.pop();
                else {
                    st.push(0);
                    break;
                }
            }
        }
        if(st.empty())
            cout << "yes" << '\n';
        else
            cout << "no" << '\n';
    }
    return 0;
}

답안 해설

문장 단위 입력을 받은 후, 문자 하나하나 확인하여 아래 기준에 맞게 분류한다.

if('알파벳소문자' || '공백')
	무시하기;
else if('(') //열린 소괄호
	push(1);
else if(')') //닫힌 소괄호
	마지막 괄호 입력(top())이 '(' 일 경우에만 pop();
else if('[') //열린 대괄호
	push(2); //1과 다른 데이터 삽입
else if(']') //닫힌 대괄호
	마지막 괄호 입력(top())이 '[' 일 경우에만 pop();

나는 문제가 원하는 '균형잡힌' 문장을 stack.size()==0인 문장으로 잡고 문제를 풀어나갔다.

문장 처음부터 하나하나 확인해나가기 때문에, 하나라도 조건에 만족하지 않는다면 바로 break;했다.
이때 최종 stack.size()==0이 되지 않도록 아무거나 삽입하고 탈출했다.

입력 종료조건은 코드 위쪽에 배치해서 while문 안의 for문을 돌지 않게끔 했다.
getline을 사용하면 " ."와 같이 공백으로 시작하고, 공백과 .으로 이루어진 짧은 문장도 문자열으로 온전히 받는다.

이 문제와 관련된 좋은 문제
BOJ 9012 (S4) 괄호
BOJ 11899 (S4) 괄호 끼워넣기

추가로 읽어보면 좋은 내용

• cpp stl stack 라이브러리 내장함수
• 문자열 문장 단위 입력 : getline(cin,str);