문자열 s에 괄호 '(', ')'와 영어 소문자가 섞여 있다고 가정해 봅시다. 이때 임의의 위치에서 여는 괄호 또는 닫는 괄호를 최소 개수만큼 삭제하여 결과 문자열이 유효한(valid) 괄호 문자열이 되도록 만들고, 그 결과로 얻을 수 있는 유효한 문자열 하나를 반환해야 합니다.
여기서 괄호 문자열이 유효하다는 것은 다음 조건 중 하나를 만족하는 경우를 말합니다.
- 문자열이 비어 있거나 소문자만 포함하는 경우
- 문자열이 AB 형태(A와 B의 연결)로 표현될 수 있고, A와 B가 모두 유효한 문자열인 경우
- 문자열이 (A) 형태로 표현될 수 있고, A가 유효한 문자열인 경우
예를 들어 입력이 s = "m)n(o)p"라면 출력은 "mn(o)p"가 됩니다. 짝이 맞지 않는 위치의 ')' 하나만 제거하면 되기 때문입니다.
문제 해결 접근 방식
이 문제는 스택(stack)과 인덱스 집합(set)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 여는 괄호 '('를 만나면 해당 인덱스를 스택에 저장합니다.
- 닫는 괄호 ')'를 만났을 때 스택이 비어 있다면 짝이 없는 괄호이므로, 그 인덱스를 제거 대상 집합에 추가합니다.
- 스택에 값이 있다면 스택에서 하나를 꺼내(pop) 짝을 맞춰줍니다.
- 모든 문자를 순회한 후, 스택에 남아 있는 인덱스(짝이 맞지 않는 여는 괄호)도 제거 대상에 포함합니다.
- 마지막으로 제거 대상 인덱스에 해당하지 않는 문자들만 모아 새로운 문자열을 만들어 반환합니다.
알고리즘 단계
- 스택과 인덱스 집합(indexes)을 초기화하고, 인덱스 변수 i를 0으로 설정합니다.
- 문자열 s의 각 문자 c에 대해 반복합니다.
- c가 '('이면 i를 스택에 push합니다.
- c가 ')'이면 스택 크기가 0일 때 i를 indexes에 추가하고, 그렇지 않으면 스택에서 pop합니다.
- i를 1씩 증가시킵니다.
- 순회가 끝나면 indexes와 스택에 남아 있는 인덱스들을 합칩니다(union).
- 0부터 len(s)-1까지 반복하면서 indexes에 없는 인덱스의 문자만 ret에 이어 붙입니다.
- ret을 반환합니다.
예제 코드 (Python)
def solve(s):
stack = []
indexes = set()
i = 0
for c in s:
if c == '(':
stack.append(i)
elif c == ')':
if len(stack) == 0:
indexes.add(i)
else:
stack.pop()
i += 1
ret = ''
indexes = indexes.union(stack)
for i in range(len(s)):
if i not in indexes:
ret += s[i]
return ret
s = "m)n(o)p"
print(solve(s))
입력
"m)n(o)p"
출력
mn(o)p
복잡도 분석
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 스택과 인덱스 집합에 최대 n개의 요소가 저장될 수 있으므로 공간 복잡도 역시 O(n)입니다. 스택을 활용해 괄호의 짝을 실시간으로 추적하는 방식 덕분에 어떤 괄호를 제거해야 하는지 정확하게 판별할 수 있습니다.