[Baekjoon, C++] 4949번 : 균형잡힌 세상

백준 단계별 풀기에서 스택 4번째 문제이다.

링크는 아래와 같다.

www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

---

백준 4949번 문제, 입력, 출력

---

백준 4949번 입력, 출력 예제

---

이 문제는, 정말 애를 많이 먹은 문제였다. 런타임에러, 출력초과, 틀렸습니다를 엄청 많이 보았기 때문이다. 접근 자체는 어렵지 않았다. 이전의 괄호 문제를 풀어 보았다면, [ ] 괄호가 하나 더 추가 된 것이였다. 그래서 ( [ 일때는 스택에 넣고, ) ] 일때는 스택의 empty 여부와 스택의 top을 확인하여 ( [ 이면 pop하는 방식을 채택하였다.

---

1. 입력을 어떻게 받을지에 대한 고민이 필요하다. 이것 때문에, 출력초과를 많이 하였다. string을 쓸 지, char[] 배열을 쓸 지에 대한 고민이 있었다. 결과를 말하자면, char[] 배열을 썼다. string 으로 한뒤 cin >> 또는 getline(cin, str) 을 썼지만, string 선언(ex. string vps;)에서 메모리 크기를 얼만큼 잡는지는 모르겠으나, 잡은 크기의 이상이 들어오는 것 같았다. 그래서 char vps[500]로 선언하고, cstring 라이브러리를 include 하였다. cstring은 strlen 함수를 사용하기 위함이다. string의 length()와 역할이 같다. 

---

2. 이 문제는 여러 문자열을 받는데, 문자열의 개수는 따로 정해두지 않았다. 그래서 반복문을 계속 돌면서 조건이 되면 탈출하게끔 하는 방식으로 구현을 한다. while(1){ · · · } 과 break를 사용한다. 탈출 조건은 문자열로 '.' 을 받을 때니까. while문 안에서 제일 처음으로 해당 조건으로 탈출을 만들어준다. if(문자열 == '.') { break; } 

---

3. 균형잡힌 세상이기 위한 조건을 생각해보자. 우리가 문자열을 처리를 마치면, 스택에 아무것도 없어야 균형잡힌 세상일 것이다. ( ) [ ] 짝을 맞춰 push 되었다가 pop 되었을 거니까. 따라서, if(스택 is empty) { yes 출력} else { no 출력 } 를 문자열 처리를 할 for문 밖에다가 그리고 while문 안에서 끝에 위치시킨다. 

---

4. 문자열을 처리를 해야한다. 괄호 문제에서 했듯이. ( [ 일때는 스택에 push하고, ) ] 일때는 스택이 비어있지 않을때 && 스택의 top이 ( [ 일때 pop한다. 그렇지 않다면, ) ] 도 push하고 break로 해당 문자열 처리를 종료한다. push하는 이유는 스택이 비어있어야 균형잡힌 세상인 조건을 만족하기 때문이다. 

 또한, 문자열을 처리하는 for문을 strlen(vps)-1 때까지 도는 것으로 한다. 처음에 strlen(vps)로 해서 틀렸습니다를 보았었다. 

 그리고, ) ]를 처리할 때, 스택 empty 여부를 고려하지 않는다면, 아마 런타임에러를 볼 수 있을 것이다. 

---

 

#include<iostream>
#include<stack>    // 표준 라이브러리 stack을 사용하기 위함
#include<cstring>
 
using namespace std;
 
int main() {
  
    while (1){
        char vps[500];       // 유저로 부터 문자열을 받을 변수 선언.
        stack<char> st;      // 스택 선언
 
        cin.getline(vps ,501);      // 값을 받는다. 출력초과 관련
 
        if (vps[0] == '.' && strlen(vps) == 1) {  // 문자열 입력 받는 while문 탈출
            break;
        }
 
        for (int j = 0; j < strlen(vps) ; j++) {
            if (vps[j] == '(' || vps[j] == '[') { // '('와 '['일때
                st.push(vps[j]);
            }
            else if (vps[j] == ')') {       // ')'일때
                if (!st.empty() && st.top() == '(') { // 스택이 비어있지 않고, 스택의 상단이 '('라면 // 런타임에러관련
                    st.pop();
                }
                else {
                    st.push(vps[j]);
                    break;           // 문자열 처리하는 for문 탈출
                }
            }
            else if (vps[j] == ']') {       // ']'일때
                if (!st.empty() && st.top() == '[') { // 스택이 비어있지 않고, 스택의 상단이 '['라면 // 런타임에러관련
                    st.pop();
                }
                else {
                    st.push(vps[j]);
                    break;           // 문자열 처리하는 for문 탈출
                }
            }
        }
        if (st.empty()) {   // 스택이 비어 있으면, 균형잡힌 세상
            cout << "yes" << endl;
        }
        else {
            cout << "no" << endl;
        }
 
    }
    return 0;
}
 

 

이상으로 4949번 문제를 마치겠다. 피드백은 환영이다.