# 코딜리티-> Brackets

문제는 아래와 같다.

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:

• S is empty;
• S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
• S has the form "VW" where V and W are properly nested strings.

For example, the string "{[()()]}" is properly nested but "([)()]" is not.

괄호가 제대로 닫혔는가를 판별해야 하는게 핵심.

먼저 생각해본건 입력으로 받은 문자열의 각 원소들(여기서는 (), {}, [])이 개별적으로 괄호가 잘 닫히는지 확인해보는 것.

다만 이방법으로 하나의 원소를 기준으로 나머지 원소들에대해서 각각 비교하며 이 괄호가 닫힐 수 있는지를 검사해야 하므로,

n^2의 시간이 소요될것이다.

해당 문제는 코딜리티 레슨에 있는 문제라 힌트가 있다. 힌트를 보니 stack and queue.

틈틈이 시간내서 생각을 해보니, stack을 이용하면 의외로 쉽게 풀릴 것 같았다. (번뜩 생각이 지나갔다...!!)

스택에 하나씩 넣으면서 가장 최근에 push 된 원소와 입력받은 문자열의 문자1개랑 비교해서 괄호가 닫힐 수 있다면 스택을 pop해주고 그렇지 않다면 문자열의 문자1개를 그대로 스택에 삽입.

이런식으로 하다보면 입력받은 문자열이 ([][]) 이런 식의 완벽하게 닫힌 형태라면 스택은 비어있을 테고, 닫힌 형태가 될 수 없다면 스택에는 원소가 남아있을 것 이다. 간단하게 샘플로 여러개의 문자열을 만들어서 손으로 풀어보면 의외로 규칙을 찾기가

쉽다. 막상 규칙을 찾고보니 쉬운데, 생각을 떠올리기가 은근히 어려웠다. 일단 풀이는 아래와 같다.

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

int Solution_Brackets(std::string &S) { std::stack<char> brackets; int strLen = S.length(); for (int i = 0; i < strLen; i++) { if (brackets.size() > 0) { char lastInputChar = brackets.top(); switch (lastInputChar) { case '(': if (S[i] == ')') { brackets.pop(); } else brackets.push(S[i]); break; case '{': if (S[i] == '}') { brackets.pop(); } else brackets.push(S[i]); break; case '[': if (S[i] == ']') { brackets.pop(); } else brackets.push(S[i]); break; } } else brackets.push(S[i]); } if (brackets.size() > 0) return 0; else return 1; }