A - Mismatched Brackets
Preview
이번 대회의 A번 문제였습니다. 그만큼 비교적 쉬운 문제였고, 가장 많은 수의 팀이 푼 문제이기도 했습니다. 하지만 오답도 꽤나 많았었는데, 그만큼 실수하기도 쉬운 문제였기 때문인 듯 합니다. 아래에서 다시 설명 드리겠지만, 총 세 종류의 경우를 따져줘야 하는데, 대부분 한두 가지 정도를 빠뜨리셨던 것 같습니다. 가장 쉬운 문제인만큼, 예제 입출력을 통해서 이를 해결할 수 있도록 했다면 좋았을텐데, 아무래도 이런 부분도 대회 진행 미숙이 아닐까 싶습니다 :( 고의로 예제에서 누락시켜서 실수를 유도한 건 아니었습니다 ^^;;
여담이지만 원래 이 문제는 출제 계획이 없었는데, 막판에 쉬운 문제에 대한 필요가 있기 때문이었습니다. 그래서 즉석에서 떠올린 문제가 이 문제였습니다. 나름대로 3종 괄호 셋트가 나오는 창의적인 문제라고 생각했었는데.. 어떠셨는지는 모르겠네요 ㅎㅎ
Problem Description
소괄호(), 중괄호{}, 대괄호[]가 섞여있는 식이 주어집니다. 이 때 주어진 식의 괄호 짝이 맞는지를 판별하는 문제입니다. 같은 종류의 괄호끼리는 서로 매치되어야 합니다.
Analysis
여러 가지 풀이 방법이 있겠지만, 가장 정석적인 방법은 스택을 이용한 풀이가 아닐까 합니다. Data structure 과목 등에서 스택에 대해 배우면서 한 번 정도는 다뤄보셨으리라 생각합니다. 알고리즘은 주어진 식을 앞에서부터 차례로 훑어보며 진행됩니다. 여는 괄호가 나오면 이를 기록해 두고, 닫는 괄호가 나오면 기록된 여는 괄호 중에서 짝을 찾아봅니다. 만일 여러 개의 여는 괄호가 있었다면 가장 마지막에 열린 괄호가 짝이 될텐데요, 즉 나중에 입력된 여는 괄호가 먼저 처리되게 됩니다. 데이터를 저장하다가, 나중에 들어온 것을 먼저 보내준다? 네, last input first out의 스택이 자연스럽게 떠오르게 됩니다.
여는 괄호가 나오면 스택에 기록을 해 두고, 닫는 괄호가 나올 때는 스택의 꼭대기를 살펴봅니다. 스택의 꼭대기에 있는 여는 괄호가 짝이 맞는(세 종류의 괄호 중) 괄호라면 두 개의 짝을 맞춰줍니다. 스택에서 한 원소를 제거하는 식으로요. 이를 쭉 진행해 나가면서, 문제가 발생한다면 식이 잘못된 것이고, 그렇지 않다면 올바른 것입니다.
발생할 수 있는 문제는 세 종류입니다. 첫 번째 문제는 앞에서 잠시 언급했던 짝이 맞지 않는 괄호의 문제입니다. 두 번째 문제는 스택의 꼭대기가 없는 경우입니다. 이 경우는 닫는 괄호는 있는데 이에 대응되는 여는 괄호는 없는 경우로, 괄호가 열리지도 않았는데 닫힌 경우입니다. 마지막 문제는 스택이 비지 않는 경우입니다. 닫는 괄호가 짝을 갖는 것도 중요하지만, 여는 괄호 역시 모두 짝이 맞아야 합니다. 알고리즘이 끝났는데 스택에 무언가가 남아있다는 것은 여는 괄호가 닫히지 않았다는 의미겠네요.
Source Code

#include<stdio.h>
char stack[10001];
char a[10001];
int top = 0;
int main(void)
{
    int l1, T;
    for(scanf("%d",&T);T>=1;T--)
    {
        scanf("%s",a);
        top = 0; // 스택 초기화
        for(l1=0;a[l1];l1++)
        {
            // 여는 괄호는 스택에 넣습니다.
            if(a[l1] == '(' || a[l1] == '{' || a[l1] == '[')
            {
                stack[top++] = a[l1];
            }
            // 닫는 괄호는 스택의 꼭대기와 짝을 맞춰봅니다.
            // 꼭대기가 없다면 에러!
            else if(a[l1] == ')')
            {
                if(top == 0) break;
                if(stack[--top] != '(') break;
            }
            else if(a[l1] == '}')
            {
                if(top == 0) break;
                if(stack[--top] != '{') break;
            }
            else if(a[l1] == ']')
            {
                if(top == 0) break;
                if(stack[--top] != '[') break;
            }
        }
        // 다 끝났는데 스택이 비지 않은 경우도 에러!
        if(a[l1] || top != 0) printf("NOn");
        else printf("YESn");
    }
    return 0;
}