[Swift] 프로그래머스 올바른 괄호의 갯수

Problem

 

코딩테스트 연습 - 올바른 괄호의 갯수

---

Solution

 

해당 문제는 다이나믹 프로그래밍을 이용해야 하는 문제입니다.

 

다이나믹 프로그래밍으로 괄호가 1쌍인 것부터 주어진 n쌍까지 차근 차근 풀어나가야 하는데요.

---

직접 구해보기

 

괄호가 1쌍일 땐 경우의 수가 -> ()만 존재합니다.

 

괄호가 2쌍일 경우 -> ()(),(()) 이렇게 두 개가 존재합니다.

 

괄호가 3쌍일 경우 -> ((())), (()()), (())(), ()(()),()()() 이렇게 5개 입니다.

 

괄호가 4쌍일 경우 -> (((()))), ((()())), ((())()), (()(())),(()()()),()((())), ()(()()), ()(())(), ()()(()),()()()(),((()))(), (()())(), (())()(), ()(())(),()()()() 이렇게 14개입니다.

 

...

 

(5쌍일 때 부터는 괄호가 어느 정도 있는지 노가다로 만들 수가 없더라구요...)

---

올바른 괄호를 만드는 규칙

 

이렇게 진행하면 현재 쌍의 올바를 괄호를 구하려면 그 전 쌍들의 올바른 괄호가 필요했습니다.

 

예를 들면 4쌍의 올바를 괄호를 구하려면 3쌍의 괄호에서 괄호 한 쌍을 추가해주면 됩니다.

 

ex) ()()() -> (()()()) , (()()) -> ((()()))

 

즉, 3쌍의 갯수만큼 더해지는 것이죠.

 

또한 1쌍과 2쌍으로 올바른 괄호를 만들고 그 뒤에 한 쌍의 괄호를 추가해주면 됩니다.

 

ex) () + ()() = ()()() -> (()()()), () + (()) = ()(()) -> (()(()))

 

즉, 이런 식으로 3쌍으로 만드는 경우의 수, 1쌍과 2쌍으로 만드는 경우의 수 이것을 반대로 한 경우의 수를 더해주면 됩니다.

 

만약 5쌍을 구하게 된다면 4쌍 * 0쌍 = 14개, 3쌍 * 1쌍 = 10개, 2쌍 * 2쌍 = 4개, 1쌍 * 3쌍 = 10개, 0쌍 * 4쌍 = 14개

-> 14+10+4+10+14 = 42개가 됩니다.

---

점화식

 

점화식으로 나타내면 짝수인 경우와 홀수인 경우로 나눌 수 있는데 

 

짝수인 경우는 아래와 같습니다.

 

dp[i] = (dp[0] * dp[i-1] + dp[1] * dp[i-2] ... dp[i/2-1]*dp[i-i/2])*2

 

반복되는 절반 지점에 곱하기 2를 해줍니다.

 

ex) 4쌍인 경우 10 + 2 + 2 + 10 -> (10 + 2)*2

 

홀수인 경우는 아래와 같습니다.

 

dp[i] = (dp[0] * dp[i-1] + dp[1] * dp[i-2] ... dp[i/2-1] * dp[i-i/2])*2 + dp[i/2]*dp[i/2]

 

 

짝수의 경우와 같이 반복되는 값을 2번 곱해주고 가운데 값을 나중에 더해줍니다.

 

 

ex) 5쌍인 경우 14 + 10 + 4 + 10 + 14 -> (14 + 10) * 2 + (4*4)

---

Source Code