LeetCode - 22. Generate Parentheses - swift

https://leetcode.com/problems/generate-parentheses/

Generate Parentheses - LeetCode

 

 

숫자 n이 주어지는데, 올바른 괄호의 짝의 개수를 뜻한다.

n이 1이면 () 이 올바른 괄호이고,

n이 2이면 ()(), or  (()) 이 올바른 괄호다. 

n이 3이면 ()()() or (())() or  ()(()) or  (()()) or ((()))  이 올바른 괄호다. 

이렇게 n이 주어질때 모든 올바른 괄호의 쌍을 출력하는 문제다.

 

 

나는 밑단에서부터 시작하는 접근법을 취했다. 

n이 1일때는 () 하나만 있다는 것이 자명하고, 

n이 2일때, n이 1일 때를 이용하여 올바른 괄호가 되게 만들도록 했다.

방법은,  

 () + n1  

 n1 + ()  

 ( + n1 + ) 

이렇게 앞에 완전한 괄호 한쌍 , 뒤에 완전한 괄호 한쌍, 앞뒤로 괄호 하나씩 넣어주면 n이 2개일 때 올바른 괄호가 생성된다.

( 중복이 발생할 수 있기 때문에, Set타입에 넣어준다 ) 

마찬가지로, n이 3일때는, n이 2개일 때, 모두 위와 같이 만들어준다. 

 

이렇게 하면 n이 4일때 틀리게 되는데, n2 + n2 인 경우도 있기 때문이다. 

이런 경우를 착안하여, 

4개일 때는 n2+n2

5개일 때는, n3+n2 ,   

6개일 때는 n4+n2,   n3+n3,  이런 경우가 존재하게 될 테고, 

arr [ N ] =  괄호의쌍이 N개일 때, 존재하는 모든 경우의 괄호 문자열 Set. 으로 정의하여, 

1부터 ~ 주어지는 n까지 모든 가능한 조합의 수를 만들어낸다.

 

 

class Solution {
    var arr = Array(repeating: Set<String>(), count: 9)
    func generateParenthesis(_ n: Int) -> [String] {
        arr[0] = [""]
       
        for i in 1...n {
            var nextSet = Set<String>()
            
            arr[i-1].forEach {
                nextSet.insert($0+"()")
                nextSet.insert("()"+$0)
                nextSet.insert("("+$0+")")
            }
            if i > 3 {
                for j in 2..<i {
                    if i-j > 1 {
                        arr[i-j].forEach { s1 in
                            arr[j].forEach { s2 in
                                nextSet.insert(s1+s2)
                            }
                        }
                    }
                }
            }
            arr[i] = nextSet
        }
        return Array(arr[n])
    }
}