문제
아래에 주어진 문법에 따라, 문자열은 소문자 단어들의 집합을 나타낼 수 있습니다.
R(expr)을 해당 표현식 expr이 나타내는 단어들의 집합이라고 합시다.
이 문법은 간단한 예제를 통해 가장 쉽게 이해할 수 있습니다.
- 하나의 문자는 그 문자 하나만을 포함하는 집합을 나타냅니다.
R("a") = {"a"}R("w") = {"w"}
- 두 개 이상의 표현식을 쉼표(
,)로 나열하면, 각 표현식이 나타내는 집합의 합집합을 구합니다.
R("{a,b,c}") = {"a","b","c"}R("{{a,b},{b,c}}") = {"a","b","c"}
두 번째 예제에서 알 수 있듯이, 최종 결과는 집합이므로 같은 단어는 한 번만 포함됩니다.
- 두 표현식을 이어 붙이면, 두 집합에서 각각 하나의 단어를 선택하여 이어 붙일 수 있는 모든 경우를 구합니다.
R("{a,b}{c,d}") = {"ac","ad","bc","bd"}
예를 들어 첫 번째 집합 {a,b}에서 하나를 선택하고, 두 번째 집합 {c,d}에서 하나를 선택하여 이어 붙입니다.
또 다른 예:
R("a{b,c}{d,e}f{g,h}")= {"abdfg", "abdfh", "abefg", "abefh", "acdfg", "acdfh", "acefg", "acefh"}
형식적으로 이 문법에는 다음 세 가지 규칙이 있습니다.
-
모든 소문자 문자
x에 대해,R(x) = {x} -
k >= 2인 표현식e1, e2, ..., ek에 대해,R({e1, e2, ...}) = R(e1) ∪ R(e2) ∪ ...즉, 각 표현식이 나타내는 집합의 합집합입니다.
-
두 표현식
e1,e2에 대해,R(e1 + e2) = {a + b | (a, b) ∈ R(e1) × R(e2)}여기서
+는 문자열 이어 붙이기(concatenation)를 의미하고,
×는 데카르트 곱(cartesian product)을 의미합니다.
즉, R(e1)에 있는 각 단어와 R(e2)에 있는 각 단어를 가능한 모든 조합으로 이어 붙입니다.
주어진 문법에 따라 단어들의 집합을 나타내는 문자열 expression이 주어집니다.
이 표현식이 나타내는 모든 단어를 사전순으로 정렬한 리스트를 반환하세요.
예시
입력:
expression = "{{a,z},a{b,c},{ab,z}}"
출력:
["a","ab","ac","z"]
설명:
각 부분을 전개하면 다음과 같습니다.
{a,z}→"a","z"a{b,c}→"ab","ac"{ab,z}→"ab","z"
따라서 전체 결과는
"a", "z", "ab", "ac", "ab", "z"가 됩니다.
하지만 최종 결과는 집합이므로 중복되는 "ab"와 "z"는 한 번만 포함됩니다.
그 후 사전순으로 정렬하면 다음과 같습니다.
["a","ab","ac","z"]
제한
- expression 문자열은 {, }, 영어 소문자, 콤마 로만 이루어진다.
- 주어진 표현식은 반드시 문법을 만족한다.
풀이
from typing import List
class Solution:
def braceExpansionII(self, expression: str) -> list[str]:
stack = []
braces = dict()
N = len(expression)
for i, ch in enumerate(expression):
if ch == '{':
stack.append(i)
elif ch == '}':
start = stack.pop()
braces[start] = i
def part_extender(part: List[str], append: List[str]):
result = []
if len(part) == 0:
return append
for p in part:
for a in append:
result.append(p + a)
return result
def parser(start: int, end: int):
whole = set()
part = []
index = start
while index < end + 1:
ch = expression[index]
if ch == '{':
part = part_extender(part, parser(index + 1, braces[index] - 1))
index = braces[index]
elif ch == ',':
for word in part:
whole.add(word)
part = []
else:
part = part_extender(part, [ch])
index += 1
for word in part:
whole.add(word)
return list(whole)
return sorted(parser(0, N - 1))접근
중괄호 안에는 다시 중괄호가 들어갈 수 있기 때문에, 표현식을 재귀적으로 파싱하는 방식으로 풀었다.
먼저 모든 {와 }의 위치를 미리 짝지어 braces에 저장한다.
for i, ch in enumerate(expression):
if ch == '{':
stack.append(i)
elif ch == '}':
start = stack.pop()
braces[start] = i스택을 사용하면 중첩된 중괄호도 안쪽부터 올바르게 매칭할 수 있다.
예를 들어
{{a,b},c}와 같은 표현식에서도 각 {가 어느 }와 대응하는지 바로 알 수 있다.
이후 parser(start, end)가 주어진 범위의 표현식을 해석한다.
part와 whole
파싱 과정에서는 두 가지 값을 관리한다.
whole = set()
part = []part는 현재 쉼표를 만나기 전까지 이어 붙이고 있는 문자열들의 집합이고,
whole은 쉼표로 분리된 각 결과를 모아 두는 합집합이다.
예를 들어
a{b,c},d에서 a{b,c}를 처리하는 동안 part는
["ab", "ac"]가 된다.
이후 ,를 만나면 현재 part의 값을 whole에 넣고 새로운 표현식을 처리하기 위해 part를 비운다.
elif ch == ',':
for word in part:
whole.add(word)
part = []따라서 쉼표는 문법에서의 합집합 역할을 한다.
문자열 연결
두 표현식이 연속해서 등장하는 경우에는 두 표현식의 가능한 결과를 모두 조합해야 한다.
이를 part_extender에서 처리한다.
def part_extender(part: List[str], append: List[str]):
result = []
if len(part) == 0:
return append
for p in part:
for a in append:
result.append(p + a)
return result예를 들어
{a,b}{c,d}에서 첫 번째 중괄호를 처리하면
part = ["a", "b"]이고, 두 번째 중괄호의 결과는
append = ["c", "d"]이다.
두 리스트의 모든 조합을 연결하면
["ac", "ad", "bc", "bd"]가 된다.
즉, 문제에서 정의한 데카르트 곱을 그대로 구현한 부분이다.
중괄호 처리
파싱 중 {를 만나면 미리 저장해 둔 braces를 이용해 대응되는 }의 위치를 찾는다.
if ch == '{':
part = part_extender(
part,
parser(index + 1, braces[index] - 1)
)
index = braces[index]중괄호 내부는 다시 하나의 완전한 표현식이므로 parser를 재귀 호출한다.
재귀 호출의 결과를 현재 part와 연결한 뒤, 현재 인덱스를 닫는 중괄호 위치까지 이동시킨다.
따라서 중첩된 표현식도 동일한 방식으로 처리할 수 있다.
일반 문자 처리
알파벳을 만나면 하나의 문자열 집합으로 보고 현재 part와 연결한다.
else:
part = part_extender(part, [ch])예를 들어 현재
part = ["ab", "ac"]이고 다음 문자가 d라면
["abd", "acd"]가 된다.
중복 제거와 정렬
whole을 set으로 관리하기 때문에 같은 문자열이 여러 경로에서 만들어져도 최종 결과에는 한 번만 포함된다.
파싱이 끝나면 마지막 part도 whole에 추가한다.
for word in part:
whole.add(word)마지막으로 전체 표현식을 파싱한 결과를 정렬해서 반환한다.
return sorted(parser(0, N - 1))결국 이 풀이는 표현식의 두 연산을 다음과 같이 대응시킨다.
,→ 결과들의 합집합- 표현식의 연속 → 가능한 문자열들의 데카르트 곱 후 연결
중괄호 내부를 재귀적으로 같은 방식으로 처리하기 때문에 임의의 깊이로 중첩된 표현식도 처리할 수 있다.
