[Swift 알고리즘] LeetCode - 22. Generate Parentheses

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

Generate Parentheses - LeetCode

 

풀이

이번 문제는 올바른 괄호가 n쌍인 모든 문자열을 구하는 문제입니다.

n=1이면 ["()"]

n=2이면 ["()()", "(())"],

n=3이면 ["((()))","(()())","(())()","()(())","()()()"] 입니다.

 

재귀를 이용해 해결했습니다.

여는 괄호(leftCount)와 닫는 괄호(rightCount)의 숫자를 각각 구합니다.

 

여는 괄호는 n가 될 때까지 뒤에 붙여주고,

닫는 괄호는 여는 괄호보다 작은동안 뒤에 붙여줍니다.

 

만약 여는 괄호 개수 + 닫는 괄호 개수가 n의 2배라면

재귀를 종료하고 result 배열에 추가합니다.

이때 굳이 leftCount와 rightCount를 이용해 개수를 계산한 이유는

String의 count는 O(n)이므로 변수 두 개로 계산하는 것이 시간 효율이 좋을 것이라고 생각했습니다.

(n의 최대값이 8이기 때문에 별 차이는 없음)

 

처음에는 ()를 이전 문자열 세트에 앞, 뒤, 감싸기를 해줬는데요.

n = 4 일 때 n2 + n2, n1 + n3같은 케이스가 발생하여 틀리더라고요.

주의하셔야 하는 부분 같습니다.. ㅠㅠ

 

전체 코드

class Solution {
    var result: [String] = []
        
    func generateParenthesis(_ n: Int) -> [String] {
        makeResult("", 0, 0, n)
        
        return result
    }
    
    func makeResult(_ current: String, _ leftCount: Int, _ rightCount: Int, _ n: Int) {
        if leftCount + rightCount == n * 2 {
            result.append(current)
            return
        }
        
        if leftCount < n {
            makeResult(current + "(", leftCount + 1, rightCount, n)
        }
        
        if rightCount < leftCount {
            makeResult(current + ")", leftCount, rightCount + 1, n)
        }
    }
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.