본문 바로가기
<알고리즘 문제풀이&연습>/[C,C++] Hackerrank

[C 자료구조] Stack - Balanced Brackets

by 사용자 BlockDMask 2017. 7. 7.
반응형

0) 제목

  • Hackerrank 의 Linked Lists 부분의 Balanced Brackets 문제입니다.

  • 스택을 이요한 괄호 맞추기? 정도 되겠습니다.

  • C언어를 이용하여 풀었습니다.

1) 문제설명

  • N개의 갯수만큼의 쿼리(줄) 을 입력받는다.

  • 각 줄은 "[{()}]" 등이 input으로 들어온다.

  • 여는괄호와 닫는괄호가 딱 맞아 떨어지면 YES를 출력하고 그렇지 않으면 NO를 출력하는 문제이다.

2) 풀이과정

  • 스택(stack)을 이용해서 풀었습니다.

  • 2가지 경우가 있다고 생각했습니다.

  • 첫 번째 경우는 여는 괄호가 들어오고 닫는 괄호와 맞지 않는 경우.

  • 두 번째 경우는 닫는 괄호만 들어오는 경우.

  • 두가지 상황을 예외라고 생각하고 문제를 풀었습니다.

3) 함수설명

  • StackInit : 스택 초기화.

  • isEmpty : 스택이 비어있는지 확인하고 비었으면 TRUE, 아니면 FALSE 반환.

  • push : 스택에 data를 집어넣고 스택의 top을 하나 증가.(top++)

  • pop : 스택에 있는 data를 빼면서 스택의 top을 감소.(--top)

  • isOpen : 문자가 (, {, [ 여는 괄호 이면 TRUE, 아니면 FALSE 반환.

  • isEqual : 문자가 ), }, ] 닫는 괄호 일때, 각 닫는 괄호에 맞는 여는 괄호가 스택의 top에 존재하는지 확인.


4) 코드

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
//문제에서 주어진 n의 범위가 10^3 까지 이고, 데이터 타입이 char 이므로 고정된 메모리로 할당한다.
#define MAX_LEN 1000
#define TRUE 1
#define FALSE 0
typedef char Data;
 
 
/////////////////////stack///////////////////// 
 
typedef struct _stack{
    Data arr[MAX_LEN];
    int top;
} Stack;
 
void StackInit(Stack * sp){
    sp->top = -1;
}
 
int isEmpty(Stack *sp){
    if(sp->top == -1return TRUE;
    return FALSE;
}
 
void push(Stack *sp, Data data){
    //check full.
    if((sp->top)+1 >= MAX_LEN) return;
    sp->arr[++(sp->top)] = data;
}
 
Data pop(Stack *sp){
    if(isEmpty(sp)) return ' ';
    return sp->arr[(sp->top)--];
}
 
Data peek(Stack *sp){
    if(isEmpty(sp)) return ' ';
    return sp->arr[(sp->top)];
}
 
 
///////////////////function///////////////////
 
int isOpen(Data data){
    if(data == '(' || data == '[' || data == '{'return TRUE;
    return FALSE;
}
 
int isEqual(Stack *stack, Data data){
    if(data == ')' && peek(stack== '('return TRUE;
    if(data == ']' && peek(stack== '['return TRUE;
    if(data == '}' && peek(stack== '{'return TRUE;
    return FALSE;
}
 
 
/////////////////////main/////////////////////
 
int main(){
    int n; 
    int len;
    int check;  //check equal brackets
    Stack stack;
    scanf("%d",&n);
    
    for(int i = 0; i < n; i++){
        check =1;
        StackInit(&stack);  //stack init.
        char* str = (char *)malloc(10240 * sizeof(char));
        scanf("%s",str);
 
        len = strlen(str);  //get length of str.
 
        for(int j=0; j<len;j++){
            if(isOpen(str[j])){ //case (, {, [, 이면 push.
                push(&stack, str[j]);
            }else if(isEqual(&stack, str[j])){  //case ),},] 일때 각각 맞는지. 맞으면 pop.
                pop(&stack);
            }else{
                check =0;
                break;
            }
        }
       
        if(check == 1 && isEmpty(&stack)){
            printf("YES\n");            
        }else{
            printf("NO\n");
        }
 
    } 
    return 0;
}
cs

5) 인증


경로 : Dashboard>Data Structures>Stacks>Balanced Brackets

출처 : [HackerRank] https://www.hackerrank.com/challenges/balanced-brackets/problem

더 나은 코드로 보완 할 곳이 있으면 말씀해주세요.

부족한 코드 많은 지적 부탁드립니다.

반응형

댓글0