Generate Parentheses

Q: Generate Parentheses의 시간 복잡도는 얼마인가요?

백트래킹 솔루션은 카탈랑 수 C(n) = (2n)! / ((n+1)! n!) 만큼의 문자열을 출력하며, 그 수는 4^n / (n^1.5 √π) 처럼 증가합니다. 각 문자열의 길이는 2n 이고 탐색 과정에서 분기를 낭비하지 않으므로, 총 시간 복잡도는 O(4^n / √n) 입니다. 추가 공간 복잡도는 현재 문자열과 호출 스택에 필요한 O(n) 에 출력 공간을 더한 것입니다.

Q: n쌍의 괄호로 만들 수 있는 올바른 괄호 문자열은 몇 개일까요?

정확히 n번째 카탈랑 수입니다. n 이 1부터 8까지일 때 1, 2, 5, 14, 42, 132, 429, 1,430입니다. 이를 이해하는 한 가지 방법은 다음과 같습니다. 모든 올바른 형식의 문자열은 ( + A + ) + B이며, 여기서 첫 번째 ( 는 해당 ) 와 짝을 이루고, A와 B는 그 사이에 n-1 개의 쌍이 있는 올바른 형식의 문자열입니다. A의 크기에 대해 합산하면 카탈랑 점화식을 얻습니다.

Q: closed < opened가 유효한 문자열을 보장하는 이유는 무엇인가요?

문자열은 짝이 맞지 않는 ( 가 앞에 없는데 ) 가 나타날 때, 즉 ) 의 개수가 ( 의 개수를 넘어설 때 잘못됩니다. closed < opened 일 때만 ) 를 허용하면 그런 일이 절대 발생하지 않고, opened < n 일 때만 ( 를 허용하면 길이가 2n 일 때 두 개수가 모두 n 에 도달합니다. 이 두 규칙을 함께 적용하면 올바른 문자열의 모든 접두사를 설명할 수 있습니다.

Q: Generate Parentheses는 재귀 없이 풀 수 있나요?

네. 두 카운터가 들어 있는 문자열인 부분 상태들을 스택에 저장하고, 같은 두 규칙으로 상태를 확장하세요. ) 확장을 ( 확장보다 먼저 푸시하면 ( 확장이 먼저 팝되어 출력이 정렬된 상태로 유지됩니다. 작업은 동일하며, 기록 관리가 호출 스택에서 직접 만든 스택으로 옮겨갈 뿐입니다.

보통백트래킹 재귀

+10

괄호 문자열은 왼쪽에서 오른쪽으로 읽었을 때 )의 개수가 (의 개수를 앞서지 않고, 끝에서 두 개수가 같으면 올바른 형식입니다. 따라서 (())()는 올바른 형식이지만, ())(는 그렇지 않습니다. 세 번째 문자가 열린 적 없는 괄호 쌍을 닫기 때문입니다.

정수 n이 주어집니다. 여는 괄호 n개와 닫는 괄호 n개로 이루어진 올바른 형식의 문자열을 모두 사전순으로 정렬하여 반환하세요. 이때 (가 )보다 앞에 옵니다.

함수

generateParenthesis(n: integer) → string-array

ninteger: 괄호 쌍의 개수
반환값string-array: n쌍으로 이루어진 모든 올바른 형식의 문자열을 사전식 순서로

제약 조건

1 ≤ n ≤ 8
n = 8의 경우 답은 문자열 1,430개입니다.

예제

입력: n = 3
출력: ["((()))", "(()())", "(())()", "()(())", "()()()"]
설명: 세 쌍은 올바른 형식으로 다섯 가지 방식으로 배열할 수 있습니다. ((()))은 세 쌍을 모두 열고 나서 닫으며, (가 먼저 정렬되므로 목록의 맨 앞에 옵니다. ()()()은 각 쌍을 즉시 닫으므로 맨 마지막에 옵니다.

입력: n = 1
출력: ["()"]
설명: 한 쌍에는 올바르게 구성된 배열이 하나 있습니다. ( 하나와 ) 하나로 이루어진 유일한 다른 문자열은 )(이며, 이는 아무것도 열려 있지 않은 상태에서 닫습니다.

제출 시 숨은 테스트 +10개

후속 질문

n쌍에 대해 올바른 형식의 문자열을 생성하지 않고 개수를 셀 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

길이가 2n인 문자열 중 올바른 형태를 갖춘 것은 일부에 불과합니다. n = 3일 때는 64개 문자열 중 5개이고, n = 8일 때는 65,536개 중 1,430개입니다. 이 문제를 해결하는 방법은 문자열을 왼쪽에서 오른쪽으로 만들면서 유효한 상태를 유지하는 문자만 추가하는 것입니다. 그러면 탐색이 끝까지 완성될 수 없는 분기로는 절대 들어가지 않습니다. 두 개의 카운터가 허용되는 문자를 결정합니다. 지금까지 추가한 (의 개수와 )의 개수입니다. 매 단계마다 )보다 (를 먼저 시도하면 문자열이 이미 정렬된 순서로 생성됩니다.

모든 문자열을 만든 다음 확인하세요

핵심 아이디어

직접적인 방법은 2n개의 위치를 가능한 모든 방식으로 채운 뒤, 올바른 형태인 문자열만 남기는 것입니다. 각 위치에는 ( 또는 )가 들어가므로 문자열은 2^(2n) = 4^n개입니다. 재귀 함수는 다음 위치에 (를 놓고 재귀 호출한 다음, 그 위치에 )를 놓고 다시 재귀 호출하며, 완성된 각 문자열은 검사를 거칩니다.

검사에서는 균형값을 사용해 문자열을 순회합니다. (에는 1을 더하고 )에는 1을 뺍니다. 균형값이 한 번도 0보다 작아지지 않고 마지막에 0이면 문자열은 올바른 형태입니다. 균형값이 0보다 작아지는 것은 닫을 열린 괄호가 없는데 )가 나온 경우로, ())(의 세 번째 문자에서 이런 일이 발생합니다.

각 위치에서 )보다 (를 먼저 시도하면 문자열이 사전순으로 나열됩니다. (가 )보다 앞서기 때문입니다. 따라서 남겨진 문자열은 이미 정렬되어 있습니다.

비용은 문자열 4^n개를 각각 O(n)에 검사하는 것입니다. n = 8이면 문자열은 65,536개이고 답은 1,430개이므로 작업의 약 98%가 버려집니다. 여기서는 n이 최대 8이기 때문에 실행을 마칠 수 있지만, 괄호 쌍이 하나 늘 때마다 작업량이 네 배로 증가합니다. 또한 첫 문자가 이미 불가능함을 보여 주는데도 )로 시작하는 문자열을 계속 만듭니다.

알고리즘

2n개의 문자를 담을 버퍼와 답을 저장할 목록을 준비합니다.
fill(pos)를 작성합니다. pos가 2n과 같으면 버퍼를 확인하고 올바른 형식이면 저장합니다.
그렇지 않으면 pos에 (를 넣고 fill(pos + 1)을 호출한 다음, 그 자리에 )를 넣고 다시 호출합니다.
문자열을 확인하려면 각 (마다 1을 더하고 각 )마다 1을 뺍니다. 균형 값이 0보다 작아지는 즉시 거부하거나, 끝났을 때 0이 아니면 거부합니다.
fill(0)을 호출하고 이미 정렬된 저장 문자열을 반환합니다.

def generateParenthesis(n):
    result = []
    path = []

    def is_balanced(text):
        balance = 0
        for ch in text:
            balance += 1 if ch == "(" else -1
            if balance < 0:
                return False  # a ")" with nothing open to close
        return balance == 0

    def fill():
        if len(path) == 2 * n:
            text = "".join(path)
            if is_balanced(text):
                result.append(text)
            return
        for ch in "()":  # "(" first keeps the output sorted
            path.append(ch)
            fill()
            path.pop()

    fill()
    return result

여는 개수와 닫는 개수를 역추적하기

핵심 아이디어

검사를 생성 과정 안으로 옮기세요. 접두사가 올바른 형태의 문자열로 이어질 수 있는 경우는 두 가지 규칙을 만족할 때뿐입니다. 여는 괄호를 최대 n개 사용하고, 닫는 괄호 )가 여는 괄호 (보다 많아지지 않아야 합니다. 따라서 각 단계에서 opened < n이면 (를 추가할 수 있고, closed < opened이면 )를 추가할 수 있습니다. 문자열의 길이가 2n에 도달하면 두 개수 모두 n이고 문자열은 올바른 형태이므로, 더 확인할 것은 없습니다.

다음은 n = 2일 때 전체 트리입니다. 빈 문자열에서는 아직 열린 괄호가 없으므로 (만 허용됩니다. (에서는 두 문자 모두 허용됩니다. (( 분기에서는 opened가 이미 2이므로 )만 들어갈 수 있습니다. 이를 두 번 추가하면 (())가 됩니다. () 분기에서는 열린 괄호가 없으므로 (만 들어갈 수 있고, 그다음에는 )가 들어가 ()()가 됩니다. 모든 분기는 답에서 끝납니다. 검색 과정에서 버려야 할 문자열은 생성되지 않습니다.

빠지는 답은 없습니다. 올바른 형태의 문자열에 속하는 모든 접두사는 두 규칙을 따르므로, 검색 과정에서 그 문자열에 다음으로 필요한 문자를 거부하지 않습니다. 또한 각 문자열의 문자들이 트리를 지나는 하나의 경로를 나타내므로, 각 문자열은 한 번씩만 생성됩니다. 순서는 첫 번째 접근 방식과 같습니다. 두 문자열의 경로는 처음 달라지는 지점에서 갈라지고, 그곳에서는 ( 분기를 먼저 탐색합니다.

모든 잎은 답이며, n쌍에 대한 답의 수는 카탈랑 수 C(n)로, 4^n / (n^1.5 √π)의 비율로 증가합니다. 모든 내부 노드는 적어도 하나의 잎으로 가는 경로에 있으므로 답 하나당 내부 노드는 최대 2n개이고, 답을 복사하는 데는 O(n)이 듭니다. 전체 비용은 O(n × C(n)) = O(4^n / √n)입니다. n = 8일 때는 65,536개를 생성한 뒤 검사하는 대신, 문자열 1,430개를 바로 생성합니다.

알고리즘

만들고 있는 문자열과 opened, closed 두 카운터를 모두 0으로 유지합니다.
문자열의 길이가 2n이면 복사본을 저장하고 반환합니다.
opened < n이면 (를 추가하고, opened + 1로 재귀 호출한 다음 제거합니다.
closed < opened이면 )를 추가하고, closed + 1로 재귀 호출한 다음 제거합니다.
빈 문자열에서 시작하여 저장된 문자열을 반환합니다. (를 먼저 시도하므로 이미 정렬되어 있습니다.

def generateParenthesis(n):
    result = []
    path = []

    def backtrack(opened, closed):
        if len(path) == 2 * n:
            result.append("".join(path))
            return
        # "(" sorts before ")", so trying it first keeps the output sorted
        if opened < n:
            path.append("(")
            backtrack(opened + 1, closed)
            path.pop()
        if closed < opened:  # only close a pair that is open
            path.append(")")
            backtrack(opened, closed + 1)
            path.pop()

    backtrack(0, 0)
    return result

함정과 경계 사례

규칙은 두 가지 비교에 담겨 있으므로, 버그는 그 비교와 두 분기의 순서에 숨어 있습니다.

closed < opened 대신 closed < n일 때 )를 허용하면 ())(와 같은 문자열이 만들어집니다. 이는 한 번도 열리지 않은 괄호 쌍을 닫습니다.
문자열에 (가 )만큼 있는지만 확인하면 )(도 허용됩니다. 균형은 마지막에만이 아니라 모든 단계에서 0 이상이어야 합니다.
(보다 먼저 )를 시도하면 올바른 문자열이 역순으로 만들어져, 정렬된 답과 비교할 때 일치하지 않습니다.
목록이나 문자열 빌더를 변경할 수 있는 언어에서 복사본 대신 공유 버퍼를 저장하는 경우: 저장된 모든 답이 같은 버퍼를 가리키게 되고, 백트래킹 과정에서 버퍼가 다시 비워집니다.
2n개의 답을 담을 고정 크기 결과 배열을 할당하거나 그 밖의 작은 크기로 어림잡는 경우: n = 8에는 답이 1,430개 있습니다. 배열을 키우거나 먼저 카탈랑 수를 계산하세요.

자주 묻는 질문4

Generate Parentheses의 시간 복잡도는 얼마인가요?

백트래킹 솔루션은 카탈랑 수 C(n) = (2n)! / ((n+1)! n!)만큼의 문자열을 출력하며, 그 수는 4^n / (n^1.5 √π)처럼 증가합니다. 각 문자열의 길이는 2n이고 탐색 과정에서 분기를 낭비하지 않으므로, 총 시간 복잡도는 O(4^n / √n)입니다. 추가 공간 복잡도는 현재 문자열과 호출 스택에 필요한 O(n)에 출력 공간을 더한 것입니다.

n쌍의 괄호로 만들 수 있는 올바른 괄호 문자열은 몇 개일까요?

정확히 n번째 카탈랑 수입니다. n이 1부터 8까지일 때 1, 2, 5, 14, 42, 132, 429, 1,430입니다. 이를 이해하는 한 가지 방법은 다음과 같습니다. 모든 올바른 형식의 문자열은 ( + A + ) + B이며, 여기서 첫 번째 (는 해당 )와 짝을 이루고, A와 B는 그 사이에 n-1개의 쌍이 있는 올바른 형식의 문자열입니다. A의 크기에 대해 합산하면 카탈랑 점화식을 얻습니다.

closed < opened가 유효한 문자열을 보장하는 이유는 무엇인가요?

문자열은 짝이 맞지 않는 (가 앞에 없는데 )가 나타날 때, 즉 )의 개수가 (의 개수를 넘어설 때 잘못됩니다. closed < opened일 때만 )를 허용하면 그런 일이 절대 발생하지 않고, opened < n일 때만 (를 허용하면 길이가 2n일 때 두 개수가 모두 n에 도달합니다. 이 두 규칙을 함께 적용하면 올바른 문자열의 모든 접두사를 설명할 수 있습니다.

Generate Parentheses는 재귀 없이 풀 수 있나요?

네. 두 카운터가 들어 있는 문자열인 부분 상태들을 스택에 저장하고, 같은 두 규칙으로 상태를 확장하세요. ) 확장을 ( 확장보다 먼저 푸시하면 ( 확장이 먼저 팝되어 출력이 정렬된 상태로 유지됩니다. 작업은 동일하며, 기록 관리가 호출 스택에서 직접 만든 스택으로 옮겨갈 뿐입니다.

Python

def generateParenthesis(n):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

입력

n = 3

기대값

["((()))", "(()())", "(())()", "()(())", "()()()"]