[BOJ] 9012 괄호

1. 문제 링크

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

2. 해설

이 문제는 여러가지 방법으로 풀이가 가능하다. stack을 사용할 수도 있고, 그냥 for문으로 문자열을 돌면서 개수를 세면서 확인이 가능하다.

둘 다 O(N)만에 해결이 가능한 방법이다.

stack을 사용한 풀이

1. 입력받은 문자열을 전부 확인하면서 '(' 라면 stack에 push한다.

2. ')' 라면 stack이 비어있는지 확인해서 비어있다면 올바르지 않다고 판단한다.

3. 비어있지 않다면 stack의 top에 '(' 가 있는지 확인하고, 있다면 '('를 pop한다.

4. 전부 확인 하고 stack이 비어있다면 올바른 괄호, 아니면 올바르지 않은 괄호임을 알 수 있다.

개수를 세면서 확인하는 풀이

1. 입력받은 문자열을 확인하면서 '(' 라면 cnt를 하나 더해주고, ')' 라면 cnt를 하나 빼준다.

2. 더하거나 빼주면서 한번이라도 cnt가 음수가 된다면 올바르지 않다고 판단한다.

3. 전부 다 확인 하고 cnt가 0이면 올바른 괄호, 아니면 올바르지 않은 괄호임을 알 수 있다.

둘 다 시간복잡도는 O(N) 만에 해결이 가능하다.

3. 소스 코드

1. stack을 사용한 풀이

#include<iostream>
#include<stack>
using namespace std;
#define MAXNUM 51

void testcase();

int main(){
    int t;
    scanf("%d", &t);
    while (t--) {
        testcase();
    }
    return 0;
}

void testcase(){
    char arr[MAXNUM]={0};
    stack<char> s;
    scanf("%s", arr);
    for (int i=0; arr[i]!=0; i++) {
        if (arr[i] == '(') {
            s.push(arr[i]);
        }
        else{
            if (!s.empty()) {
                if (s.top() == '(') {
                    s.pop();
                }
            }
            else{
                s.push(')');
                break;
            }
        }
    }
    
    printf("%s\n", s.empty() ? "YES" : "NO");
}

2. 개수를 세면서 확인하는 풀이

#include<iostream>
#define MAXNUM 51

void testcase();

int main(){
    int t;
    scanf("%d", &t);
    while (t--) {
        testcase();
    }
    
    return 0;
}

void testcase(){
    char arr[MAXNUM]={0};
    int cnt=0;
    bool isRight = true;
    scanf("%s", arr);
    for (int i=0; arr[i]!=0; i++) {
        cnt += arr[i] == '(' ? 1 : -1;
        if (cnt < 0) {
            isRight = false;
            break;
        }
    }
    if (cnt != 0) {
        isRight = false;
    }
    
    printf("%s\n", isRight ? "YES" : "NO");
}

4. 추가 언급

1. 이 문제에서 많은 사람들은 문자열을 다 확인하고 옳은 괄호인지 판단하는데, 중간 중간 마다 틀린 괄호라는 판단을 안해주어 틀리는 경우가 대부분이다. 이 판단을 stack에서는 empty로, cnt는 음수로 하였다. 

2. 이 문제에 대한 언급은 아니지만 코드에 대한 언급을 살짝 하자면 필자는 testcase 문제가 나오면 이렇게 함수를 이용해서 문제를 푼다. 이는 stack메모리에 잡히는 특징을 이용해서 초기화를 따로 해주지 않아도 되는 이점 때문이다. 예를 들어 다음 코드를 보자.

while (t--) {
        scanf("%s", arr);
        for (int i=0; arr[i]!=0; i++) {
            if (arr[i] == '(') {
                s.push(arr[i]);
            }
            else{
                if (!s.empty()) {
                    if (s.top() == '(') {
                        s.pop();
                    }
                }
                else{
                    s.push(')');
                    break;
                }
            }
       }
        
       printf("%s\n", s.empty() ? "YES" : "NO");
}

이렇게 코드가 있을 때 문제점은 무엇일까?

바로 NO라는 답이 나오고 나서 그 다음 testcase에서 사용할 s라는 stack에는 ')' 가 들어가 있기 때문이다. 즉 완전히 시작할 때 마다 stack을 완전히 비워줘야 하는 것이다. 그래서 코딩코스트를 조금 줄이고자 testcase()라는 함수를 사용해서 바로 초기화를 해주었다.

이렇게 코드를 짜자! 라는 것을 말하고자 하는 것이 아니다. 여러분이 풀기 편한 방식대로 풀면 된다. 하지만 testcase문제들이 나온다면 초기화를 언제나 생각하고, 조심해야한다는 것을 잊지 말아주었으면 한다.