[BOJ] 10799. 쇠막대기 (C)

*스택 자료구조 구현 연습을 위해 C로 풀이 

*() 는 레이저이므로 레이저가 나올 때마다 스택에 있는 [(] 의 개수만큼 더해준다. (쇠막대기가 잘라지니까)

*[(]는 스택에 푸시 (레이저는 푸시 안함)

*[)]는 스택에서 팝하는데 이때, sum++ 을 해줘야 한다. 

 

((()()))

이렇게 있다면 보기 편하게 레이저를 *로 치환한다. 

( (* *) ) 

이렇게 될 것이다. 

그럼 막대는 

( (* *) )

  ---    -> - - -

------ -> -- -- --

이렇게 되는 데 레이저를 만날 때마다 스택에 있는 개수만큼 막대의 개수가 증가하게 된다. 

막대의 끝을 의미하는 [)]가 나올 때는 나누어진 막대의 가장 오른쪽 개수를 세야 하기 때문에 sum++을 해준다. 

 

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

#include <stdio.h> #include <stdlib.h> #include <string.h>   #define MAXX 100001   struct Stack{     int top;     char array[MAXX]; };   int isFull(struct Stack *st) {     if (st->top == MAXX-1) return 1;     return 0; } int isEmpty(struct Stack *st) {     if (st->top == 0) return 1;     return 0; } void push(struct Stack* st, char data) {     if(isFull(st)) return;       st->array[++st->top] = data; } int pop(struct Stack *st) {     if (isEmpty(st))return -1;     return st->array[st->top--]; } int peek(struct Stack *st){     if (isEmpty(st)) return -1;     return st->array[st->top]; } int main(){       struct Stack *st = (struct Stack*)malloc(sizeof(struct Stack));       char op[MAXX], nop[MAXX];       scanf("%s", op);       int sum = 0;           for (int i = 0; i < strlen(op); i++) {         if (op[i] == '(') {             if (op[i+1] == ')') {                 //레이저라면                 if (isEmpty(st)) {                     i++;                     continue;                 }                 sum += st->top;                 i++;             }             else push(st, op[i]);         }         else if (op[i] == ')'){             pop(st);             sum++;         }     }     printf("%d", sum);           free(st); }