[Algorithm] 해커랭크 - Stacks: Balanced Brackets

https://www.hackerrank.com/challenges/ctci-balanced-brackets/problem

( ), { }, [ ] 로 이루어진 String이 주어졌을 때, 이 괄호 문자열이 Balanced 인지 판별하는 문제다.

이 문제에서 말하는 Balanced는 한번 열린 괄호가 짝이 맞춰지면서 모두 닫히는 조건을 말한다.

괄호 문제는 Stack 자료구조를 활용하면 쉽게 풀 수 있다. 열린 괄호가 입력되면 Stack에 넣고, 닫힌 괄호가 입력되면 Stack의 맨 위 요소와 쌍이 맞는지 확인하고 Stack에서 제거하는 방식으로 진행하면 된다.

코드 상에서 Balanced 한 조건을 판별하기 위해서는 다음과 같은 조건을 갖추면 된다.

1. 닫힌 괄호인 경우 Stack이 비어있지 않은지 체크한 후, 비어있지 않다면 Stack의 맨 위 요소와 짝이 맞으면 된다.

2. 모든 작업이 끝나고 Stack이 비어있어야 된다.

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

bool is_opener(char bracket) {     bool isOpener = false;     if(bracket =='{'|| bracket =='(' || bracket =='[')     {         isOpener = true;     }     else     {         isOpener = false;     }     return isOpener; } bool is_matching(char opener, char closer) {     bool isMatching = false;     if (opener=='{')     {         if (closer=='}')         {             isMatching = true;         }         else         {             isMatching = false;         }     }     else if(opener=='(')     {         if (closer==')')         {             isMatching = true;         }         else         {             isMatching = false;         }     }     else if(opener=='[')     {         if (closer==']')         {             isMatching = true;         }         else         {             isMatching = false;         }     }     else     {         isMatching = false;     }     return isMatching; } bool is_balanced(string expression) {     bool isBalanced = true;     int length = expression.length();     stack<char> expressions;     for (int i = 0; i < length; i++)     {         if(is_opener(expression[i]))         {             expressions.push(expression[i]);         }         else if(!expressions.empty())         {             if(is_matching(expressions.top(),expression[i]))             {                 expressions.pop();             }             else             {                 isBalanced = false;                 break;             }         }           else         {             isBalanced = false;             break;         }     }     if(!expressions.empty())     {         isBalanced = false;     }     return isBalanced; } Colored by Color Scripter

cs

생각나는 그대로 코드를 작성하니 쉬운 알고리즘인데도 코드가 꽤 길다.

다른 코드를 보니 더 간결한 코드가 있었는데, 살펴보니 열린 괄호가 들어오면 그 짝이 맞는 닫힌 괄호를 Stack에 넣고, 닫힌 괄호가 들어오면 같은지만 확인는 방식으로 코딩을 했었다.

내 코드의 경우 일일히 모든 조건을 함수를 호출해서 비교하게 했으므로 길어졌다.

* 코드 작성 중 문제점

 스택이 비어있을 경우를 확인하지 않아 런타임 에러가 발생하였다.

 모든 비교가 끝난 뒤 스택이 비어있어야 되는 조건을 검사하지 않았다.