문제 소개
소문자 알파벳과 괄호 "(" , ")" 로 구성된 문자열 s가 주어졌다고 가정해 보겠습니다. 이때 괄호로 묶인 모든 문자열을 재귀적인 방식으로 뒤집고, 그 결과 문자열을 반환하는 것이 목표입니다.
예를 들어 입력이 s = "back(aps)ce"라면, 괄호 안의 "aps"가 뒤집혀 "spa"가 되므로 최종 출력은 "backspace"가 됩니다.
해결 전략
이 문제는 스택(Stack)과 방향성 탐색 함수를 조합하면 깔끔하게 해결할 수 있습니다. 먼저 여는 괄호와 닫는 괄호의 짝 위치를 미리 매핑해 두고, 탐색 도중 괄호를 만나면 진행 방향을 반대로 전환하여 해당 구간을 역순으로 읽어 들입니다. 이 덕분에 중첩된 괄호도 자연스럽게 처리할 수 있습니다.
trav() 함수 정의
trav() 함수는 s, dir, start, close, ans를 매개변수로 받으며 다음과 같이 동작합니다.
- end := dir이 -1이면 "(", 그렇지 않으면 ")"
- other := end가 ")"이면 "(", 그렇지 않으면 ")"
- start가 문자열 길이보다 작고 s[start]가 end가 아닌 동안 반복합니다.
- s[start]가 other와 같다면 → trav(s, -dir, close[other][start] - dir)을 재귀 호출한 뒤, start := close[other][start] + dir로 갱신합니다.
- 그 외의 경우 → ans의 끝에 s[start]를 추가하고, start := start + dir로 이동합니다.
메인 함수의 처리 흐름
- ans := 새로운 리스트를 생성합니다.
- close := 키 ")"와 "("를 가지며, 값이 각각 빈 맵인 새로운 맵을 생성합니다.
- stack := 새로운 리스트를 생성합니다.
- 문자열 s의 각 인덱스 i와 문자 c에 대해 다음을 수행합니다.
- c가 "("이면 → i를 스택에 push합니다.
- c가 ")"이면 → 스택의 top을 o로 꺼내고(pop), close[")"][i] := o, close["("][o] := i를 설정합니다.
- trav(s, 1, 0)을 호출합니다.
- ans를 빈 문자열로 연결(join)하여 반환합니다.
Python 구현 예제
class Solution:
def solve(self, s):
ans = []
close = {")": {}, "(: {} }
stack = []
for i, c in enumerate(s):
if c == "(":
stack.append(i)
elif c == ")":
o = stack.pop()
close[")"][i] = o
close["("][o] = i
def trav(s, dir, start, close=close, ans=ans):
end = "(" if dir == -1 else ")"
other = "(" if end == ")" else ")"
while start < len(s) and s[start] != end:
if s[start] == other:
trav(s, -dir, close[other][start] - dir)
start = close[other][start] + dir
else:
ans.append(s[start])
start += dir
trav(s, 1, 0)
return "".join(ans)
ob = Solution()
print(ob.solve("back(aps)ce"))
입력
"back(aps)ce"
출력
backspace
동작 원리 상세 설명
코드가 실제로 어떻게 동작하는지 단계별로 살펴보겠습니다.
- 괄호 짝 매핑: enumerate()로 문자열을 순회하면서 여는 괄호의 인덱스를 스택에 쌓습니다. 닫는 괄호를 만나면 스택에서 가장 최근의 여는 괄호 인덱스를 꺼내, 서로의 짝 관계를 close 딕셔너리에 양방향으로 기록합니다.
- 순방향 탐색 시작: trav(s, 1, 0)은 인덱스 0부터 오른쪽 방향으로 탐색을 시작합니다.
- 괄호를 만나면 방향 전환: 일반 문자는 그대로 ans에 추가하지만, 여는 괄호 "("를 만나면 해당 괄호의 짝인 닫는 괄호 바로 앞 위치부터 역방향으로 재귀 탐색을 수행합니다. 이 과정에서 괄호 내부의 문자들이 뒤집힌 순서로 ans에 추가됩니다.
- 중첩 괄호 처리: 역방향 탐색 중에 또 다른 괄호를 만나면 같은 방식으로 방향을 전환하므로, 몇 겹으로 중첩된 괄호도 올바르게 처리됩니다.
시간 및 공간 복잡도
모든 문자는 정확히 한 번씩만 방문되므로 시간 복잡도는 O(n)입니다. 괄호 짝을 저장하는 딕셔너리, 스택, 결과 리스트 모두 문자열 길이에 비례하여 사용되므로 공간 복잡도 역시 O(n)입니다.