Generate Parentheses
괄호 문자열은 왼쪽에서 오른쪽으로 읽을 때 )의 개수가 (의 개수를 앞서지 않고, 끝에서 두 개수가 같으면 올바른 괄호 문자열입니다. 따라서 (())()는 올바른 괄호 문자열이지만, ())(는 그렇지 않습니다. 세 번째 문자가 한 번도 열리지 않은 쌍을 닫기 때문입니다.
정수 n이 주어지면 여는 괄호 n개와 닫는 괄호 n개로 이루어진 모든 올바른 괄호 문자열을 사전순으로 정렬해 반환하세요. 여기서 (가 )보다 앞에 옵니다.
함수
- ninteger
- 괄호 쌍의 개수
- 반환값string-array
- 사전순으로 나열된 n쌍의 모든 올바른 문자열
제약 조건
1 ≤ n ≤ 8-
n = 8일 때 답은 문자열 1,430개입니다.
예제
- 입력
- n = 3
- 출력
- ["((()))", "(()())", "(())()", "()(())", "()()()"]
- 설명
- 세 쌍은 올바른 형식의 문자열 다섯 개를 만듭니다.
((()))은 세 쌍을 모두 먼저 열기 때문에 가장 먼저 정렬되고,()()()은 각 쌍을 즉시 닫기 때문에 마지막에 옵니다.
- 입력
- n = 1
- 출력
- ["()"]
- 설명
- 한 쌍에는 올바른 형식의 문자열이 하나 있습니다. 유일하게 가능한 다른 배열인
)(는 무엇인가 열리기도 전에 닫힙니다.
후속 질문
n쌍의 올바른 문자열을 직접 생성하지 않고도 개수를 셀 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
문자열을 왼쪽에서 오른쪽으로 읽으면서 열려 있는 쌍의 개수를 세어 보세요. 그 개수가 0보다 작아진다면 무엇이 잘못된 것일까요?
문자열을 한 번에 한 문자씩 만드세요.
(를n개보다 적게 배치했다면(를 추가할 수 있고,)를(보다 적게 배치했다면)를 추가할 수 있습니다. 이런 방식으로 만든 문자열은 언제나 완성할 수 있습니다.두 개의 카운터
opened와closed를 사용해 재귀적으로 처리하세요.)분기보다(분기를 먼저 시도하고, 호출이 반환된 후 각 문자를 제거한 다음, 길이가2n에 도달하면 문자열을 저장하세요.(를 먼저 시도하면 출력이 정렬된 상태로 유지됩니다.
풀이
길이가 2n인 문자열 중 올바른 형식인 것은 극히 적습니다. n = 8일 때 65,536개 중 1,430개입니다. 각 문자열을 왼쪽에서 오른쪽으로 만들고, 접두사를 아직 완성할 수 있을 때만 문자를 추가하세요. 두 개의 카운터로 이를 판단하며, (를 )보다 먼저 시도하면 문자열이 정렬된 순서로 나옵니다.
모든 문자열을 만든 다음 확인하세요
핵심 아이디어
2n개의 위치를 (와 )의 모든 조합으로 채우면 4^n개의 문자열이 생기며, 이 중 올바른 형식의 문자열만 남기세요. 문자열을 확인하려면 균형값을 사용해 문자열을 순회하세요. (에는 1을 더하고 )에는 1을 빼세요. 균형값이 0 아래로 내려가지 않고 0으로 끝나면 올바른 형식입니다. 각 위치에서 (를 )보다 먼저 배치하면 문자열이 정렬된 순서로 나열됩니다.
각 문자열을 확인하는 데 O(n)이 듭니다. n = 8이면 문자열은 65,536개이고 답은 1,430개이므로, 작업량의 약 98%가 버려지며 괄호 쌍이 하나 추가될 때마다 작업량은 네 배로 늘어납니다.
알고리즘
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일 때 (( 분기는 두 번 닫을 수밖에 없어 (())를 만들고, () 분기는 열고 닫을 수밖에 없어 ()()를 만듭니다. 각 문자열은 트리를 지나는 하나의 경로이므로 한 번씩 나타나며, ( 분기가 먼저 진행되므로 출력은 정렬된 순서입니다.
모든 리프는 답이므로 작업량은 출력 크기에 비례합니다. O(4^n / √n).
알고리즘
- 만들고 있는 문자열과
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 이상을 유지해야 합니다. (보다)를 먼저 시도하는 것. 올바른 문자열이 역순으로 나옵니다.- 리스트나 문자열 빌더처럼 변경 가능한 경우, 공유 버퍼의 복사본이 아니라 공유 버퍼 자체를 저장하는 것. 그러면 저장된 모든 답이 같은 버퍼를 가리키고, 백트래킹 과정에서 버퍼가 다시 비워집니다.
- 작은 어림값으로 고정 크기 결과 배열을 정하는 것.
n = 8에는 답이 1,430개 있습니다.
자주 묻는 질문3
Generate Parentheses의 시간 복잡도는 얼마인가요?
백트래킹은 카탈랑 수인 C(n) = (2n)! / ((n+1)! n!)개의 문자열을 출력하며, 이 수는 4^n / (n^1.5 √π)의 비율로 증가합니다. 각 문자열을 만들고 복사하는 데 O(n)이 걸리므로, 시간 복잡도는 O(4^n / √n)입니다. 추가 공간 복잡도는 현재 문자열과 호출 스택에 대해 O(n)이며, 여기에 출력 공간이 더해집니다.
n쌍의 괄호로 만들 수 있는 올바른 괄호 문자열은 몇 개일까요?
1부터 8까지의 n에 대한 n번째 카탈랑 수: 1, 2, 5, 14, 42, 132, 429, 1,430. 올바른 형식의 모든 문자열은 ( A ) B로 나뉘며, 여기서 해당 )는 첫 번째 (와 짝을 이루고 A와 B는 n - 1쌍을 공유합니다. A의 크기에 대해 합산하면 카탈랑 점화식이 나옵니다.
Generate Parentheses를 재귀 없이 풀 수 있나요?
네. 각 상태를 두 카운터가 포함된 문자열로 나타내어 부분 상태 스택에 저장하고, 동일한 두 규칙으로 각 상태를 확장하세요. ( 확장이 먼저 꺼내져 출력이 정렬된 상태로 유지되도록 ) 확장을 ( 확장보다 먼저 넣으세요.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def generateParenthesis(n):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
인자
n = 3
예상 출력
["((()))", "(()())", "(())()", "()(())", "()()()"]