4949) 15. 스택 : 균형잡힌 세상(The Balance of the World)

문제

https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

 

풀이

   문제 설명이 구체적이지 않아 어디가 문제인지 모르겠는 문제. '균형'이란 것의 정의가 모호해서 나의 경우 처음에는 ( ), [ ] 가 한 쌍인 경우만 체크하는 줄 알고 그렇게 코드를 짰다. 결과는 오답. 다시 문제를 읽고 일반 문자열도 이 균형이란 것이 적용된다길래 yes/no가 좀 더 포괄적으로 출력되게 만들면서, 공백이나 개행 문자의 경우는 무시하고 마침표가 입력될 때까지 입력을 받도록 만들었다. 그게 아래의 코드이다.

#include "cstdio"
#include "string.h"
#include "stack"
using namespace std;

void pCheck(stack<char>* pStack, char ps) {
    // '(' or '[' 찾기
    if(ps == '(' || ps == '[') pStack->push(ps);
    else if(ps == ')' || ps == ']') {
        if(!pStack->empty()) {
            char temp = pStack->top();
            
            if(((temp == '(') && (ps == temp + 1)) || ((temp == '[') && (ps == temp + 2))) pStack->pop();
        }
        else pStack->push(ps);
    }
}

int main() {
    char ps[101]{};
    
    while(true) {
        bool endCheck(false);
        
        for(int i(0); ps[i] != '\0'; i++) ps[i] = '\0';				// 배열 초기화
        for(int i(0); i < 101; i++) {
            ps[i] = getchar();
            if(ps[i] == '\n') i--;								// 개행문자는 제거함
            if(ps[i] == '.' && ps[i + 1] == '\n') {
                if(i) {										// '.' 이 처음으로 들어온 게 아닐 경우
                    endCheck = true;
                    break;
                }
                else return 0;
            }
        }
        
        if(endCheck) {									// 마침표가 찍힌 경우에만 괄호 탐색을 시작함
            stack<char> pStack;
            
            for(int i(0); ps[i] != '.'; i++) {
                if(ps[i] == '(' || ps[i] == ')' || ps[i] == '[' || ps[i] == ']') pCheck(&pStack, ps[i]);
            }
            
            if(pStack.empty()) printf("yes\n");
            else printf("no\n");
        }
    }
}

 

   그런데 이것도 틀렸다. 예제는 물론 백준 질문란이나 사람들이 제시하는 어지간한 반례를 다 넣어도 문제가 없었는데 계속 틀렸다고만 하니 환장할 노릇... 그래서 정답 처리된 사람들의 코드를 넣고 테스트 케이스를 돌려봤다. 내 코드와의 차이점은

 

1. 공백, 개행문자 또한 yes로 처리
2. 마침표가 아닌 엔터로 yes/no 판단해 출력

이었다. 아니 줄의 구분을 마침표로 한다는 얘기는 '\n'이 아닌 '.'으로 입력 완료를 구분한다는 뜻 아닌가? 예제처럼 "( abcd )." 처럼 마침표를 찍지 않고 "( abcd )\n" 로 입력해도 받아주면 대체 마침표는 종료할 때 빼곤 왜 필요한 거지..? 이것 때문에 코드를 5번은 엎은 것 같다. 그래서 괜히 처음에 getchar()를 썼다가 cin.getline으로 바꾸고, 이게 개행을 기준으로 하나의 문자열로 받아서 마침표로 기준을 잡기 위해 끝에 ignore도 붙였다가, string을 썼다 char를 썼다 정말 여러 가지 했는데...

   두 가지의 괄호와 그 안의 내용이 대칭인지(ex. ( hello ). (O) / ( hello). (X))를 명시하던가, 마침표는 그냥 우리가 볼 때만 한 줄의 구분점으로 삼고, 실제 입력할 땐 마침표가 입력의 종료를 의미하지 않는다고 하던가 설명하면 좋을 것을.. 열 받는다. 그래서인지 풀이 후기를 쓰는 지금 기준으로 정답률이 36.116%밖에 안된다. 이다음 문제는 29%던데 좀 걱정된다.

 

   어쨌든 이 코드가 정답으로 처리된 코드이다.

#include "iostream"
#include "stack"
using namespace std;

bool pCheck(stack<char>* pStack, char ps) {
    // '(' or '[' 찾기
    if(ps == '(' || ps == '[') pStack->push(ps);
    else if(ps == ')' || ps == ']') {
        if(!pStack->empty()) {
            char temp = pStack->top();
            
            if(((temp == '(') && (ps == ')')) || ((temp == '[') && (ps == ']'))) pStack->pop();
            else return false;
        }
        else return false;
    }
    
    return true;
}

int main() {
    string ps;
    
    while(true) {
        bool flag(true);				// 함수 호출됬는지 여부로 괄호 존재 판단
        stack<char> pStack;
        
        getline(cin, ps);
        if(ps == ".") return 0;
        
        int len = ps.length();
        
        for(int i(0); i < len; i++) {
            if(ps[i] == '(' || ps[i] == ')' || ps[i] == '[' || ps[i] == ']') flag = pCheck(&pStack, ps[i]);
            if(!flag) break;
        }
        
        if(flag && pStack.empty()) printf("yes\n");
        else printf("no\n");
    }
}

 

이건 다른 분이 짠 더 빠른 코드