문제

풀이

괄호 문자열인지, 아닌지 판단하는 문제이다.
그걸 판단하는 함수를 vps()라고 한다면, input을 넘겨주고 맞으면 1, 아니면 0을 리턴하는 식으로 풀이를 생각했었다. (그러나 리팩토링 따위는 하지 않지)

간단하게 stack을 이용해서 풀 수 있다고 생각했다.

• '(' => stack에 넣기
• ')' => stack에서 뽑기.
  이 때, stack이 비어있는 상태에서 뽑으려고 하면 break하며 NO.

위의 로직을 수행한 후, stack이 비어 있다면 YES, 아니라면 NO.

검색한 것

how to empty a char array? - init()에서 stack 배열을 초기화하기 위해 사용했다.

코드

먼저 stack을 구현하기 위해 가장 간단한 array 구조로 stack을 구현하였고, IsEmpty(), push(), pop()을 구현하였다.

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

#define MAX_STACK_SIZE 51

char stack[MAX_STACK_SIZE];
int top=-1;

void init(){
  top = -1;
  memset(stack, 0, MAX_STACK_SIZE);
} 

int IsEmpty(){
  if(top<0)
    return 1;
  else
    return 0;
}

void push(char value){
  stack[++top]=value;
}
 
char pop(){
  if(IsEmpty()==1)
    return 'f';
  else 
    return stack[top--];
}
int main(){
  int N,i,j;

  scanf("%d",&N);

  // memory allocation
  char **arr = malloc(sizeof(char*)*N);
  for(i=0;i<N;i++){
    arr[i] = malloc(sizeof(char)*MAX_STACK_SIZE); //eos 때문에 +1크기로 하는걸로 알고 있음
  }
  
  // read data
  for(i=0;i<N;i++){
    scanf("%s",&arr[i][0]);
  }

  // logic start
  int length;
  char res;
  for(i=0;i<N;i++){
    init();
    length = strlen(arr[i]);
    res = 0;
    for(j=0;j<length;j++){
      if(arr[i][j] == '('){
        push('(');
      }else if(arr[i][j] == ')'){
        res = pop();
        if(res == 'f'){
          printf("NO\n");
          break;
        }
      }
    }
    if(res != 'f'){
      if(IsEmpty())printf("YES\n");
      else printf("NO\n");
    }
  }



  return 0;
}

딱히 어려운 건 없고 더 깔끔하게 짤 수 있는데 시간이 없으니까 넘어간다.