•
문제 설명 : 소괄호가 포함된 문자열 s 에서, 괄호쌍이 아닌 괄호 문자를 제거한 문자열을 반환한다.
•
풀이 방법
◦
문자열을 순차적으로 순회 시, 닫힌 괄호()) 는 가장 마지막에 나온 열린 괄호(( ) 와 매핑되어야한다.
◦
따라서, 열린 괄호에 대한 정보를 FILO을 따르는 스택 방식으로 저장하기로 했다.
◦
아래 조건에 해당하는 괄호 문자는 삭제처리한다.
▪
매핑할 ( 가 없는 ) 문자
▪
순회 후, 매핑이 안된 (
•
시간복잡도 :
•
성공 코드
아래 코드에서는, 삭제 대상 인덱스를 따로 저장했다.
문제를 푼 후 확인해보니 동작 시간이 꽤 긴 편이라 다른 해결법도 확인해보니, 굳이 delete_index를 별도로 저장하지 않고 삭제 대상 인덱스를 빈 문자로 설정 후, 이후 join 을 사용하여 합쳐주는 방식을 사용하니, 훨씬 빠르게 처리가 가능하였다.
아무래도 아래 코드는 extend 나 별도 순회를 하면서 result 연산도 진행되어 오래 걸린 듯 하다.
# O(N + N + N) -> O(N)
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
open_round_brackets = []
delete_index = []
result = ""
# 문자열 순회 -> O(N)
for i in range(len(s)):
if s[i] == '(':
open_round_brackets.append(i)
elif s[i] == ')':
if open_round_brackets:
open_round_brackets.pop()
else:
delete_index.append(i)
# O(len(open_round_brackets)) -> O(N)
delete_index.extend(open_round_brackets)
# 문자열 재순회 -> O(N)
for i in range(len(s)):
if i not in delete_index:
result += s[i]
return result
Python
복사