[BaekJoon/백준] 9012번 스택 활용

VPS 라는 문자열 조건을 체크하는 문제.

상쇄 조건을 체크하는 문제다.

 

 

첫 번째로, 그냥 풀어보았다!

#include <stdio.h>
#include <string.h>

char str[51]; // 하나는 널문자 여유.. ㅎㅎ
int N;

int main() {
    int value = 0; // 항상 0보다 크거나 같음을 유지하면서 반복문을 돌아야함.
    scanf("%d", &N);

    for(int i = 0; i < N; i++) {

        value = 0;
        scanf("%s", str);

        for(int j = 0; j < strlen(str); j++) {

            if(value < 0)
                break;

            if(str[j] == '(')
                value++;
            if(str[j] == ')')
                value--;


        }
        if(value == 0)
            printf("YES\n");
        else
            printf("NO\n");
    }
}

/*
 앞에서 나온 ( 갯수와, 따라 나오는 ) 의 갯수는 서로 상충되는 관계다.

 
 앞에서 ( 가 나온만큼 )가 나와야 VPS가 된다.
 그래서 value 변수를 두고, ( 일시 ++, ( 일시 -- 를 통해 value 변수값을 조절한다.
 
 반복문 내에서 value 변수가 0보다 작은 경우가 되면, 앞에서 (가 나온 만큼 뒤에서 )가 나오지 않은 상황이므로 바로 반복문을 종료한다.
 
 그리고 반복문이 끝났을 때, value == 0이면 둘의 상쇄가 잘 이루어진 것이므로 YES, 그게 아니라면(0보다 크거나 0보다 작거나) 상쇄가 잘 이루어지지 않은 것이므로 NO.
 
 */

스택을 쓰지 않고도 나름 기발하게 생각해내서 풀었다고 느껴서 정말 뿌듯했다!!!

 

 

근데 이걸 스택으로도 풀 수 있다고 하는데 도저히 모르겠어서, 다른 분의 풀이를 참고했는데, 놀라웠다.. 난 이런생각을 하질 못했다.

알고 나니 간단한 것만 같은데, 난 생각을 못했다..

 

여튼 그렇게해서 스택으로도 다시풀어보았다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int *stack;
    int size;
}IntStack;

void push(IntStack *s, int a) {
    s->stack[s->size++] = a;
}
int pop(IntStack *s) {
    if(s->size <= 0)
        return -1; // 데이터 없을 시 -1
    
    --s->size;
    
    return 0; // 성공 시 0
}

int N;
char input[51];

int main() {
    int i, j;
    IntStack st;
    st.stack = calloc(51, sizeof(int));
    st.size = 0;
    
    scanf("%d", &N);
    
    for(i = 0; i < N; i++) {
        
        st.size = 0; // 매번 초기화
        scanf("%s", input);
        
        for(j = 0; j < strlen(input); j++) {
            if(input[j] == '(') {
                push(&st, 1);
            }
            else if(input[j] == ')') {
                if(pop(&st) == 0)
                    ;
                else
                    break;
            }
        }
        // 배열을 끝까지 안 돈 경우 = 중간에 break or 상쇄가 되지 않은 경우
        if( j != strlen(input) || st.size != 0)
            printf("NO\n");
        else
            printf("YES\n");
    
    }
    
}