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

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

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

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

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

 

((()()))

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

( (* *) ) 

이렇게 될 것이다. 

그럼 막대는 

( (* *) )

  ---    -> - - -

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

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

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

 

 

#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); }