[programmers][2020카카오공채] 괄호 변환

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

---

문자열 p를 입력으로 받은 경우 먼저 p에서 문자열 u, v 분리한다.

분리하는 방법은 cnt 변수를 하나두고 p를 앞에서부터 탐색하면서 여는괄호가 나오면 cnt+1, 닫는괄호가 나오면 cnt-1해준다.

탐색하면서 탐색의 시작지점(p[0])을 제외하고 cnt가 0이 되는 지점이 나오면 이를 기준으로 p를 u, v로 분리한다.

 문자열 p는 '(', ')' 개수가 같은 균형잡힌 괄호 문자열이라는 조건이 있기 때문에 cnt가 0이 되는 지점은 반드시 존재한다.ex) p = "(())()" 인 경우 인덱스가 3일때 cnt를 계산하면 cnt가 0이되고 이를 기준으로 "(())" "()"문자열로 분리한다. 분리한 문자열 중 앞에 있는 문자열 "(())"이 u, 뒤에 있는 문자열 "()"이 v가 된다.

 

문자열 u, v를 구했으면 u가 올바른 괄호 문자열인지 판단한다.

올바른 괄호 문자열인지 판단하는 전형적인 방법은 스택을 이용하는 것이지만 u가 균형잡힌 괄호 문자열이므로 cnt 변수로 구할 수 있다.

마찬가지로 문자열을 앞에서부터 탐색하면서 여는괄호인 경우 cnt+1, 닫는괄호인 경우 cnt-1 연산을 한다.

균형잡힌 괄호 문자열이기 위해서는 닫는 괄호가 짝이 되는 여는 괄호보다 앞에 나오면 안된다. ex) )(

즉, cnt가 음수가 되는 경우 올바른 괄호 문자열이 아니게된다.

 

u가 올바른 괄호 문자열인 경우 u + solution(v)

올바르지 않은 괄호 문자열인 경우 "(" + solution(v) + ")" + u 

가 정답이 된다.

 

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/2020카카오공채/괄호 변환.cpp