[백준 9012번] 괄호 (C++, Python)

이번 포스트에서는 백준 알고리즘 문제인 괄호 문제를 리뷰하겠습니다.

 

이 문제는 solved.ac 기준 실버 4에 위치한 문제입니다.

 

먼저 문제입니다.

테스트 케이스 개수인 T를 입력받고 T개의 괄호 문자열을 입력받습니다.

이때, 주어진 괄호 문자열이 올바른 괄호 문자열인지 판별하여 "YES" 혹은 "NO"를 출력하는 문제입니다.

 

올바른 괄호 문자열을 만들려면 다음과 같은 조건들이 있습니다.

• 여는괄호 로 시작하여야함.
• 닫히지 않은 괄호가 1개라도 있을 때 닫는괄호 사용이 가능함
• 닫는괄호와 여는괄호의 개수가 같음

따라서, 위 조건을 스택의 원리에 빗대어 생각해보면

여는 괄호는 PUSH 연산을 수행하고, 닫는 괄호는 POP 연산을 수행합니다.

 

1번 조건은 스택이 공백일 때 POP 연산을 할 수 없다 고 정의할 수 있습니다.

2번 조건 역시 스택이 공백일 때 POP 연산을 할 수 없다 고 정의됩니다.

3번 조건은 괄호 입력이 끝났을 때, 스택은 공백이어야 합니다.

 

그렇기에 이번 문제는 스택을 사용하여 문제를 해결합니다.

 

해당 문제는 다음과 같은 순서로 진행됩니다.

1. 테스트 케이스 개수 T를 입력받습니다.
2. T번 반복문을 돌면서 괄호 문자열을 입력받습니다.
3. 해당 괄호가 실패했는지 확인을 위한 논리변수 isFalse를 생성합니다. 이때, 초기값은 False 입니다.
4. 입력받은 괄호 문자열의 길이만큼 반복문을 돌면서 다음을 수행합니다.
   1. 괄호 문자열의 현재 인덱스 위치의 값이 ( 라면 PUSH 연산을 수행합니다.
   2. 괄호 문자열의 현재 인덱스 위치의 값이 ) 라면 스택이 공백인지 검사하여 공백이라면 NO를 출력하고 isFalse를 True로 설정한 후 반복문을 탈출합니다. 스택이 공백이 아니라면,  POP 연산을 수행합니다.
5. 스택이 공백이 아니라면, NO를 출력하고 isFalse를 True로 설정합니다.
6. isFalse가 False라면 YES를 출력합니다.
7. 스택이 공백이 아니라면, 스택이 공백이 될 때 까지 POP 연산을 수행합니다.

언어 별로 조금씩 내용이 다를 수 있으나 위의 알고리즘과 동일합니다.

 

아래는 C++ 코드입니다.

 

#include <iostream>
#include <cstring>
 
using namespace std;
 
int stack[100] = {0,};
int top = 0;
 
int main() {
    int n;
    cin >> n;
    
    for(int i = 0; i < n; ++i) {
        char temp[51];
        bool isFault = false;
        cin >> temp;
        int length = strlen(temp);
        for(int k = 0; k < length; ++k) {
            if(temp[k] == '(') {
                stack[top] = 1;
                top++;
            }
            if(temp[k] == ')') {
                if(top > 0) {
                    stack[top] = 0;
                    top--;
                }
                else {
                    cout << "NO" << endl;
                    isFault = true;
                    break;
                }
            }
        }
        if(top > 0 && !isFault)
            cout << "NO" << endl;
        else if(top == 0 && !isFault)
            cout << "YES" << endl;
 
        top = 0;
    }
 
    return 0;
}

다음은 Python 코드 입니다.

 

stack = []
 
def push(n) :
    stack.append(n)
 
def pop() :
    stack.pop(-1)
 
def isEmpty() :
    if len(stack) == 0 :
        return True
    else :
        return False
 
t = int(input())
 
for i in range(t) :
    tmp = input()
    isNo = False
    length = len(tmp)
    for k in range(length) :
        if tmp[k] == '(' :
            push(1)
        else :
            if isEmpty() == True :
                print("NO")
                isNo = True
                break
            pop()
    if isEmpty() == False :
        print("NO")
        isNo = True
 
    if isNo == False :
        print("YES")
 
    if isEmpty() == False :
        for i in range(len(stack)) :
            pop()

해당 문제는 괄호와 스택과의 연관성을 빠르게 찾아낼 수 있다면, 풀이하기 쉬운 문제였습니다.

다음 포스트에서 또 다른 문제 풀이로 찾아오겠습니다. 감사합니다.