프양연 괄호 / 구현, 스택?

1. 스택으로도 풀림 2. 아이디어 구현으로 풀어도 됨 3. 스택으로 풀이한 것 찾아보기

#include <stdio.h> //#define N_MAX 1000 #define N_MAX 11 char arrayC[N_MAX + 1]; int arrayN[N_MAX + 1]; int tempN[N_MAX + 1]; typedef struct { int a; int b; } reverse; reverse reverseN[10]; int reverseCnt; void reverseOp(int a, int b) { for (int i = a; i <= b; i++) { tempN[i] = arrayN[i]; } for (int i = b, j = a; i >= a; i--) { arrayN[j++] = -tempN[i]; } reverseN[reverseCnt].a = a; reverseN[reverseCnt].b = b; reverseCnt++; } int main(void) { freopen("input.txt", "r", stdin); int test_case; int T, N; setbuf(stdout, NULL); scanf("%d", &T); for (test_case = 1; test_case <= T; ++test_case) { scanf("%d %s", &N, arrayC); if (N % 2 == 1) { printf("#%d %d\n", test_case, -1); continue; } else if (N == 0) { printf("#%d %d\n", test_case, 0); continue; } for (int i = 0; i < 10; i++) { reverseN[i].a = 0; reverseN[i].b = 0; reverseCnt = 0; } for (int i = 0; i < N; i++) { if (arrayC[i] == '(') arrayN[i] = 1; else arrayN[i] = -1; } // 가장 낮은 값을 찾아서 전부 +Y 로 그래프가 되도록 변경 int sum = 0; int max = 0; int max_i = -1; for (int i = 0; i < N; i++) { sum += arrayN[i]; if (sum < 0 && max > sum) { max = sum; max_i = i; } } // 반전 시키자 if (max_i != -1) { reverseOp(0, max_i); } // 최종 높이를 구하자 int back_sum = 0; int back_height = 0; for (int i = 0; i < N; i++) { back_sum += arrayN[i]; } back_height = back_sum / 2; if (back_height == 0) { printf("#%d %d\n", test_case, 0); continue; } else if (back_height == 1) { for (int i = N - 1; i >= 0; i--) { if (arrayN[i] == 1) { reverseOp(i, i); break; } } } else { back_sum = 0; for (int i = N - 1; i >= 0; i--) { back_sum += arrayN[i]; if (back_sum == back_height) { reverseOp(i, N - 1); break; } } } printf("#%d %d\n", test_case, reverseCnt); for (int i = 0; i < reverseCnt; i++) { printf("%d %d\n", reverseN[i].a, reverseN[i].b); } } return 0; }

#include <stdio.h> //#define MAX_N 1100 #define MAX_N 11 char input[MAX_N]; char testInput[MAX_N]; int cutInput[MAX_N]; int L; int top; int stack[MAX_N]; void stackInit(void) { top = 0; } int stackIsEmpty(void) { return (top == 0); } int stackPush(int value) { stack[top] = value; top++; return 1; } int stackPop(int *value) { if (top == 0) { //printf("stack is empty!"); return 0; } top--; *value = stack[top]; return 1; } int getDiff(int a, int b) { int result = a - b; if (result < 0) result = (-1) * result; return result; } void doCheck() { int i, j = 0; int value; int idx1, idx2; int cntLeft = 0, cntRight = 0; // ( : push // ) : pop -> 실패시 새로운 배열에 입력 stackInit(); for (i = 0; i < L; i++) { if (input[i] == '(') { stackPush(i); } else if (input[i] == ')') { if (stackPop(&value) == 0) { cutInput[j] = i; testInput[j] = ')'; j += 1; } } } cntLeft = j; while (1) { if (stackPop(&value) == 0) break; cutInput[j] = value; testInput[j] = '('; j++; } cntRight = j - cntLeft; // ')' 입력완료 if (cntLeft == 0) { // (((((( printf("%d\n", 1); printf("%d %d\n", cutInput[(cntRight / 2) - 1], L - 1); return; } else if (cntRight == 0) { // )))))) printf("%d\n", 1); printf("%d %d\n", 0, cutInput[(cntLeft / 2) - 1]); return; } idx1 = cutInput[cntLeft - 1]; printf("%d\n", 2); printf("0 %d\n", idx1); if (cntLeft == cntRight) { idx2 = L / 2; } else if (cntLeft < cntRight) idx2 = cutInput[j / 2]; else { int size = idx1; for (i = 0; i < cntLeft / 2; i++) { int temp = getDiff(size, cutInput[cntLeft - 1 - i]); cutInput[cntLeft - 1 - i] = getDiff(size, cutInput[i]); cutInput[i] = temp; } idx2 = cutInput[j / 2]; } printf("%d %d\n", idx2, L - 1); } int main(void) { int test_case, T; int result = 0; freopen("input.txt", "r", stdin); setbuf(stdout, NULL); scanf("%d", &T); for (test_case = 1; test_case <= T; ++test_case) { scanf("%d", &L); scanf("%s", input); if (L % 2 == 1) { printf("#%d %d\n", test_case, -1); } else { printf("#%d ", test_case); doCheck(); } } return 0; //정상종료시 반드시 0을 리턴해야 합니다. }