[programmers][월간 코드 챌린지 시즌2] 괄호 회전하기

문제 : programmers.co.kr/learn/courses/30/lessons/76502

---

문자열 길이는 1,000으로 그다지 길지않다.

가능한 모든 문자열을 구해서 각 문자열들이 올바른 괄호문자열인지 판단 후 올바른 괄호문자열의 수를 센다.

올바른 괄호문자열은 문자열을 앞에서부터 탐색하면서 열린괄호라면 스택에 넣는다.

만약 닫는 문자열이 나왔다면 stack이 비어있지 않고 stack의 top에 있는 괄호와 올바른짝이라면 올바른 괄호짝이므로 stack을 pop해주고 다음 문자를 탐색해나간다. 만약 닫는 문자열이 나왔는데 stack이 비어있거나 (ex, ] ) 올바른 괄호짝이 아니라면 (ex, ((] ) 올바른 괄호문자열이 될 수 없다.

모든 문자열을 탐색했을 때 스택이 비어있다면 올바른 괄호 문자열이다. 만약 탐색이 끝났어도 스택이 비어있지 않다면 짝을 가지지 못하는 열린 괄호가 남아있다는 이야기이므로 올바르지 않은 괄호 문자열이다.

 

시간복잡도는 문자열 길이가 N이라면 O(N^2).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/%EC%9B%94%EA%B0%84%20%EC%BD%94%EB%93%9C%20%EC%B1%8C%EB%A6%B0%EC%A7%80%20%EC%8B%9C%EC%A6%8C2/%EA%B4%84%ED%98%B8%20%ED%9A%8C%EC%A0%84%ED%95%98%EA%B8%B0.cpp