9012) 15. 스택 : 괄호(Parenthesis)

문제

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

9012번: 괄호

 

풀이

   벡터도 써봤다, 동적 배열도 써봤다, 50짜리 고정 배열도 써봤다, 아예 스택 구조를 안 쓰는 등 삽질을 많이 했다. 문제를 보고 '(' 와 ')' 의 개수가 같은 대신 처음에 ')'만 들어오지 않으면 된다는 아이디어에 갇혀 '(' 만 세는 Lcount, ')'만 세는 Rcount 이렇게 나눠서 세게 하고 돌리는데 뭔가 버퍼가 제대로 비워지지 않는 느낌을 받았다. 결과는 당연히 오답..ㅠ

 

   여러 테스트 케이스를 넣어보고 고민하다 C++ STL에서 스택을 제공한다는 것을 일찍도 깨달아서 이걸 써보기로 했다. 사용 방법은 벡터 쓰듯이

std::stack<type> varName;

 

이렇게 쓰면 된다. main으로만 퉁치려다 예외 사항을 내 코드를 이용해 체크하려면

 

1. 일부러 배열(or 스택)에 값을 넣거나
2. 변수를 만들어 예외일 때 조건문을 바꿔 타도록 하거나
3. bool 함수로 만들어 반환값을 적절히 넣어주거나

셋 중 하나를 타야했다. 1번과 2번은 돌릴 때 뭔가 불안정한 느낌이었고 실제로 오답으로 채점되었기에 3번으로 만들기로 했다. 이제야 떠오른 발상의 전환이 바로 Lcount, Rcount 따로 셀 필요 없이, Lcount ==  Rcount 는 Lcount - Rcount = 0 이니까 스택에 적용하면, push / pop / empty 가지고도 충분하겠다는 것.. 그렇게 코드를 짜서 다행히 맞췄다.

#include "cstdio"
#include "stack"

// Test Case 1 : ((())))(())
// Test Case 2 : ((ab!=0)&&(((a+b)%2)=0)) / ((ab!=0)&&(((a+b)%2)=0)

bool isVPS(std::stack<char> pStack) {
    char ps('\0');
    while(ps != '\n') {
        ps = getchar();
        if(ps == '(') pStack.push(ps);				// Lcount (count++)
        else if(ps == ')') {
            if(!pStack.empty()) pStack.pop();		// Rcount (count--)
            else {
                while(getchar() != '\n');				// 앞에서 이미 갯수가 같은데 또 ')'가 들어온 상황. 버퍼를 비우고
                return false;						// NO 라고 반환함
            }
        }
    }
    
    if(pStack.empty()) return true;				// Lcount - Rcount = 0
    return false;
}

int main() {
    int repeat(0);
    std::stack<char> pStack;
    
    scanf("%d%*c", &repeat);
    
    for(int i(0); i < repeat; i++) {
        if(isVPS(pStack)) printf("YES\n");
        else printf("NO\n");
    }
    
    return 0;
}

 

 

 

아래는 스택없이 계산해보려던 코드.

#include "cstdio"

int main() {
    int repeat(0);
    
    scanf("%d%*c", &repeat);
    
    for(int i(0); i < repeat; i++) {
        int count(0);
        char ps('\0');
        
        for(int j(0); ps != '\n'; j++) {
            ps = getchar();
            
            if(j == 0 && ps == ')') {
                count--;
                while(ps != '\n') ps = getchar();
                break;
            }
            
            if(ps == '(') count++;
            else if(ps == ')') count--;
        }
        
        if(count == 0) printf("YES\n");
        else printf("NO\n");
    }
    
    return 0;
}