Leetcode Generate Parentheses

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

간단하게 1~8 범위에서 모든 올바른 괄호 쌍을 출력하는 문제이다.

n이 1~8이므로 dfs를 이용한 완전탐색을 이용하였다.

dfs코드를 설계하기 위해서 먼저 규칙을 생각하였다.

1. 처음 위치엔 '(' 밖에 올 수 없다.

2. '(' 를 하나 사용한다면, ')' 도 하나 사용해야 한다.

3. '(' 와 ')' 를 모두 사용했다면 하나의 케이스가 생성된다.

1번과 2번 규칙을 이용하기 위해 dfs의 파라미터에 사용 가능한 왼쪽 괄호 개수와 오른쪽 괄호 개수인 left와 right를 넣기로 하였다.

또한 출력이 String 기반이므로 StringBuilder를 이용하여 괄호 문자열을 조작하였다.

class Solution {
    fun generateParenthesis(n: Int): List<String> {
        val answer = mutableListOf<String>()
        val case = StringBuilder()

        dfs(n, 0, case, answer)
        return answer
    }

    fun dfs(left: Int, right: Int, case: StringBuilder, answer: MutableList<String>){
        if(left == 0 && right == 0){
            answer.add(case.toString())
            return
        }

        if(left > 0){
            dfs(left - 1, right + 1, case.append('('), answer)
            case.deleteCharAt(case.lastIndex)
        }

        if(right > 0){
            dfs(left, right - 1, case.append(')'), answer)
            case.deleteCharAt(case.lastIndex)
        }
    }
}

dfs코드는 위처럼 구성하였다.

dfs(n, 0, case, answer)로 호출하여 먼저 n개의 '('를 준비하였고, dfs에서 '('를 하나 소모할 때마다 left 를 하나 줄이고 right 를 하나 늘리도록 하였다.

')'를 소모할 경우 right만 하나 줄이도록 하였다.

left와 right를 모두 소모할 경우 answer에 case를 하나 추가하도록 하였다.