LeetCode 22. Generate Parentheses

https://leetcode.com/problems/generate-parentheses/description/?source=submission-ac

문제

---

생각하기

---

동작

단순히 DFS 백트래킹 문제로 해결하려고 했으나 최적화하지 않으면 풀 수 없는 문제였다.

일단 괄호의 짝이 맞도록 구현이 필요하다.

여는 괄호의 개수가 닫는 괄호보다 많을 경우에 닫는 괄호를 추가함으로써 괄호 연결 과정에서 오류가 생기지 않는다.

나는 괄호를 만드는 모든 과정을 만들고 난 뒤에 올바른 괄호 조합인지 검사하는 방식으로 했지만, 괄호를 생성할 때부터 올바른 괄호로 만들어지도록 해야 한다.

결과

코드

---

import java.util.ArrayList // 필요에 따라 Kotlin의 MutableList 사용 가능

class Solution {
    // 결과 리스트는 클래스 멤버로 유지
    private lateinit var ansList: MutableList<String>
    private var maxPairs: Int = 0 // n 값을 저장할 변수

    fun generateParenthesis(n: Int): List<String> {
        ansList = ArrayList() // 결과 리스트 초기화
        this.maxPairs = n

        // 백트래킹 함수 호출 (현재 문자열, 사용한 여는 괄호 수, 사용한 닫는 괄호 수)
        backtrack(StringBuilder(), 0, 0)
        return ansList
    } // End of generateParenthesis()

    private fun backtrack(currentString: StringBuilder, openCount: Int, closeCount: Int) {
        // 1. 종료 조건: 문자열 길이가 2*n 이 되면 완성된 조합
        if (currentString.length == maxPairs * 2) {
            ansList.add(currentString.toString())
            return
        }

        // 2. 여는 괄호 추가 시도
        // 여는 괄호는 n개까지 추가 가능
        if (openCount < maxPairs) {
            currentString.append('(')
            backtrack(currentString, openCount + 1, closeCount)
            currentString.deleteCharAt(currentString.length - 1) // 백트래킹: 마지막 문자 제거
        }

        // 3. 닫는 괄호 추가 시도
        // 닫는 괄호는 현재까지 사용된 여는 괄호 수보다 적을 때만 추가 가능
        if (closeCount < openCount) {
            currentString.append(')')
            backtrack(currentString, openCount, closeCount + 1)
            currentString.deleteCharAt(currentString.length - 1) // 백트래킹: 마지막 문자 제거
        }
    } // End of backtrack()
} // End of Solution class