[백준] 9012.괄호

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

입출력

Input
6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

Output
NO
NO
YES
NO
YES
NO

풀이

이 문제는 스택으로 풀 수 있다. VPS의 특성을 생각해보면,

1. 한번 열린 괄호는 반드시 닫혀야 한다.( '(' )
2. 닫힌 괄호는 열린 괄호보다 먼저 올 수 없다.
3. 모든 괄호에는 짝이 있어야 한다.

두 가지를 스택에 적용시키면, 다음과 같이 해결할 수 있다.

1. 열린 괄호가 올 경우, 스택에 PUSH한다.
   2-1. 닫힌 괄호가 열린 괄호보다 먼저 오는 경우, VPS를 만족하지 않는다.
   2-2. 2-1이 아닌 경우, 스택에서 POP한다.
2. 모든 과정이 끝났을 때, 스택은 비어있어야 한다.

위 과정으로 문제를 해결했다.

코드

#include <iostream>
#include <stack>
#include <cstring>

using namespace std;

bool checkVPS(char *command){
    stack<char> parenthesis;


    for(int i = 0; i < strlen(command); i++){
        if(command[i] == ')'){
            if(parenthesis.empty()) {
                return false;
            }
            else parenthesis.pop();
        }
        else{
            parenthesis.push(command[i]);
        }
    }   

    return parenthesis.empty();
}

int main(){
    int numberOfCommand = -1;
    cin >> numberOfCommand;
    char commandLine[51];
    char *command = commandLine;

    for(int i = 0; i < numberOfCommand; i++){
        cin >> command;
        if(checkVPS(command)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

후기

• 처음에는 계속해서 runtime error(NeverBeNull)를 받았는데, 생각해보니 입력받는 command 문자열의 포인터에 사이즈를 할당해주지 않아서 생긴 에러였다.
  

• 틀렸다는 메세지가 계속해서 나왔는데, 명령을 입력받는 문자열의 길이가 문제였다. 문제에서는 괄호로 되어있는 명령문의 길이가 2<= length <= 50으로 되어 있었는데, 50개의 괄호가 입력될 경우 문자열 마지막에 \0가 입력될 수 없기 때문에 계속 틀렸다는 문구를 받았다. 입력 문자열의 길이를 51로 변경한 이후 정답을 받을 수 있었다.

• 처음에는 표시만 잘 하자는 의미로 Stack의 타입을 int로 받았는데, 생각해보니 int type은 4byte이고, char type은 1byte이니 메모리 활용면에서 char type을 이용하는 것이 효율적이라고 생각해서 변경했다.

풀이와 후기 이외에 다른 알고리즘이 있거나, 코드에서 불필요한 부분이나 더 효율적으로 사용할 수 있는 부분이 있다면 말씀해주세요.